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


Chvátal, V. "The Strong Perfect Graph Theorem."

Referenced on Wolfram|Alpha

Graph Antihole

Cite this as:

Weisstein, Eric W. "Graph Antihole." From MathWorld--A Wolfram Web Resource.

Subject classifications