Talk:Strong perfect graph theorem

	This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:
Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Mid This article has been rated as Mid-priority on the project's priority scale.

Is this what an "odd antihole" means?

Latest comment: 1 month ago2 comments2 people in discussion

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