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 2002, p. 225)
or to include them (Cook 2012, 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
