Recognizing Partitionability

A graph G is ( p,k) -partitionable if its maximum stable set is of size p , its maximum clique is of size k and for each node v , G -v has both a k -colouring and p -clique cover.
[1] Let p :=max{1x:xTH(G)} and k :=max{1x:xTH(G )} . We can find (close enough) estimates of these integers in polytime, using the ellipsoid algorithm to optimize over the theta body. Then p will be our "proxy" for the maximum stable set size α (G) and k the proxy for the maximum clique size ω (G) .
[2] If | V(G)|kp+1 then G is not a ( p,k) -partitionable graph.

[3] Potatope * Slicing Proposition:

If G is ( p,k) -partitionable, then TH p (G):=TH(G){x:1x=p} is a simplex with integral vertices.

[4] The proposition is the heart of the algorithm. It is obvious for minimally imperfect graphs and the proof is easy for partitionable graphs (it uses the same ideas of Bland, Huang, Trotter and Padberg). We now use the ellipsoid algorithm to either find affinely independent integral vectors a 1 ,a 2,a | V(G)| in TH p (G) or show it has a fractional extreme point. (This algorithm is very similar to several routines in Gr\"otschel, Lov\'asz, Schrijver.) Similarly, we either deduce non-partitionability of G , or we find integer vectors b 1 ,b 2, in TH k (G ) .
[5] We may now determine partitionability as follows. Let A be the matrix whose i th row is a i . For each a i , find some j such that a i b j=0 - if there is no such, then G is not partitionable. Let b j be the i th column of a second matrix B . Finally, if A B=J-I , then G is ( p,k) partitionable. Otherwise it is not.
  (*) Vasek Chv\'atal came up with the name "potatope" for the theta body since it can have smooth parts and pointy bits.