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.