For , let be a skew partition of , where there are no edges between and , and is complete to . For each , choose one of , say , and let be the union of all these . Call a chunk. If there is an odd hole or antihole in , then it belongs to the chunk (for some choice of the 's), so to check Bergeness of , it is enough to check Bergeness of all the chunks. But even if is linear in the size of , the number of chunks can be exponential. Maybe there is a way around this. With decomposition theorems that come up from excluded minors, using separations instead of skew partitions, the same exponential blowup happens, but it can be avoided by using separations that are pairwise noncrossing - then you only get linearly many pieces. Is there an analogous nice way for skew partitions to fit together, so that we only get linearly many (or polynomially many) chunks?
Contributed by Paul Seymour
Back to the main index for Perfect Graphs.