Graph Antihole

The graph complement of a graph hole. Graph antiholes are called even if they have an even number of vertices and odd if they have an odd number of vertices (Chvátal). No odd antihole is a perfect graph (since the clique number of an antihole with 2k+1 vertices is k and its chromatic number is k+1).

See also

Berge Graph, Chordless Cycle, Graph Cycle, Graph Hole, Strong Perfect Graph Theorem

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Chvátal, V. "The Strong Perfect Graph Theorem." https://users.encs.concordia.ca/~chvatal/perfect/spgt.html.

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Graph Antihole." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphAntihole.html

Subject classifications