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.