One can think of algorithms for testing for odd holes if you use only 2-joins to decompose a graph, or if you use only skew partitions. However, the interaction between skew partition steps and 2-join steps adds another level of difficulty. Can one argue that this can be reduced only to testing for holes as you decompose using skew partitions only and testing for holes using 2-joins only?
Contributed by Jeremy Spinrad
Similar approach worked in algorithms for recognizing even-hole-free graphs: first the graph is decomposed via vertex cut-sets, and only then via 2-joins. The 2-join decomposition blocks are defined in such a way that no new vertex cut- set is introduced.
Contributed by Kristina Vuskoic
Back to the
main index
for Perfect Graphs.