TOPICS
Search

Graph Hole


Chvátal defines the term hole to mean "a chordless cycle of length at least four." The restriction "of length at least four" allows use of the term "hole" regardless of if the definition of "chordless cycle" is taken to already exclude cycles of length 3 (e.g., West 2002, p. 225) or to include them (Cook 2012, p. 197; Wikipedia).

Graph holes are called even if they have an even number of vertices and odd if they have an odd number of vertices. The graph complement of a hole is called a graph antihole. No odd hole is a perfect graph (since the clique number of an odd hole is 2 and its chromatic number is 3).


See also

Berge Graph, Chordless Cycle, Graph Antihole, Graph Cycle, 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.Cook, K.; Eschen, E. M.; Sritharan, R.; and Wang, X. "Completing Colored Graphs to Meet a Target Property." In Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers.Ed. A. Brandstädt, K. Jansen, and R. Reischuk). Berlin, Germany:â-¢Springer, pp. 189-200, 2013.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.Wikipedia contributors. "Induced Path." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia. Aug. 7, 2020; retreived Sep. 4, 2020. https://en.wikipedia.org/wiki/Induced_path.

Referenced on Wolfram|Alpha

Graph Hole

Cite this as:

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

Subject classifications