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).

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.