Odd Chordless Cycles

An odd chordless cycle is a chordless cycle of length >4.

A graph is said to be perfect 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 perfect. 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

Chordless Cycle, Odd Number, Perfect Graph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Odd Chordless Cycles." From MathWorld--A Wolfram Web Resource.

Subject classifications