TOPICS
Search

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

References

Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.

Referenced on Wolfram|Alpha

Graph Antihole

Cite this as:

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

Subject classifications