Interaction Between Different Skew-Partitions in a Graph

For $1 \le i \le n$, let $(A_i,B_i,C_i,D_i)$ be a skew partition of $G$, where there are no edges between $A_i$ and $B_i$, and $C_i$ is complete to $D_i$. For each $i$, choose one of $A_i,B_i,C_i,D_i$, say $X_i$, and let $X$ be the union of all these $X_i$. Call $G \setminus X$ a chunk. If there is an odd hole or antihole in $G$, then it belongs to the chunk (for some choice of the $X_i$'s), so to check Bergeness of $G$, it is enough to check Bergeness of all the chunks. But even if $n$ is linear in the size of $G$, 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.