A graph hole, called a "hole" by Chvátal, is 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 2000, p. 225) or to include
them (Cook et al. 2013, p. 197; Wikipedia).
A graph hole is called even if it has an even number of vertices and is an odd
hole if it has 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 ,
Odd Hole ,
Strong
Perfect Graph Theorem
Explore with Wolfram|Alpha
References Chvátal, V. "The Strong Perfect Graph Theorem." https://users.encs.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. Aug. 7, 2020; retrieved 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
