Talk:Strong perfect graph theorem

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Is this what an "odd antihole" means?

One sentence reads as follows:

"Similarly, he observed that perfect graphs cannot contain odd antiholes, induced subgraphs complementary to odd holes: an odd antihole with 2k + 1 vertices has clique number k and chromatic number k + 1, which is again impossible for perfect graphs."

This sentence seems to define an "odd antihole" as an induced subgraph complementary to an odd hole (a cycle of odd length). But then it immediately refers to "an odd antihole with 2k + 1 vertices" — which appears to say that an odd antihole itself must have the odd number of 2k + 1 vertices, rather than its complement.

I hope someone familiar with graph theory will clarify this confusing definition. 2601:204:F181:9410:F954:F279:738C:BD96 (talk) 18:12, 27 June 2025 (UTC)[reply]

Complementing a graph doesn't change its number of vertices. —David Eppstein (talk) 00:52, 28 June 2025 (UTC)[reply]