Skew -Partitions of Balanced Size

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 $e_1, \ldots, e_k$ of it add a vertices $v_1,\ldots,v_k$ s.t. each $v_i$ has degree $2$ and is adjacent to both ends of $e_i$.

Back to the main index for Perfect Graphs.