The problem with recursive skew decomposition is that at least at first glance, you get exponential behavior. This would not occur if you were always able to find a decomposition in which each of A,B,C,D have at least n/c vertices for some c. Call this a skew partition of balanced size.

a) Can you find a skew partition of balanced in polynomial time, if one exists?

b) Will always looking for a balanced skew partition if possible lead to a polynomial size decomposition tree for perfect graphs (ie always use the skew partition which maximizes the size of the smallest set)

Contributed by Jeremy Spinrad

Answer: There exists a graph admitting no skew-partition of balanced size: take a clique and for some edges of it add a vertices s.t. each has degree and is adjacent to both ends of .

Back to the
main index
for Perfect Graphs.