decomposition blocks. What if we could
prove that it is enough to consider only two blocks for each skew-partition. Would
that imply a polynomial size decomposition tree? Possibly introducing new endblocks or using cleaning? (Kristina Vuskovic).
The problem with using skew-paritions (or star cutsets) for recognition algorithms is that the decomposition tree they induce does not have polynomial size. The following questions have been suggested during the workshop:
1. Suggest different endblocks of the decompostition (other than basic perfect graphs), that can be recognized in polynomial time and yet make the decomposition tree polynomial (Bruce Reed)
2. Normally every skew-partition has decomposition blocks. What if we could
prove that it is enough to consider only two blocks for each skew-partition. Would
that imply a polynomial size decomposition tree? Possibly introducing new endblocks or using cleaning? (Kristina Vuskovic).
3.Does decomposition of 
-free graphs via star-cutsets induce a polynomial size decomposition tree? Possibly using cleaning? (Kristina Vuskovic).
Back to the
main index
for Perfect Graphs.