TOPICS
Search

Odd Chordless Cycle


An odd chordless cycle, also called an odd hole, is a chordless cycle whose length is an odd number greater than 4.

By König's line coloring theorem, the line graph of a bipartite graph is a perfect graph and hence has no odd chordless cycles. It can nevertheless contain triangles and therefore need not itself be a bipartite graph.

A graph is a perfect graph iff neither the graph G nor its graph complement G^_ has an odd chordless cycle. A graph with no 5-cycle and no larger odd chordless cycle is therefore automatically a perfect graph. This is true since the presence of a chordless 5-cycle in G^_ corresponds to a 5-cycle in G and G^_ can have no chordless 7-cycle or larger since the diagonals of these cycles in G^_ would contain a 5-cycle in G.


See also

Bipartite Graph, Chordless Cycle, König's Line Coloring Theorem, Line Graph, Odd Number, Odd Hole, Perfect Graph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Odd Chordless Cycle." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OddChordlessCycle.html

Subject classifications