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. West, D. B. Introduction
to Graph Theory, 2nd ed. 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 https://mathworld.wolfram.com/GraphHole.html
Subject classifications
