2-divisible Graphs

A 2 division of a graph is a partition of its vertex set into two parts neither of which contains a maximum clique. Hoang and McDiarmid call a graph 2-divisible if all of its induced subgraphs permit 2-division. Every perfect graph is 2-divisible, and an odd hole has no 2-division. Thus 2-divisible graphs are odd-hole-free.

Hoang and McDiarmid made the following conjectures:

(1) G is 2-divisible iff G is odd-hole-free

Contributed by Bruce Reed

Back to the main index for Perfect Graphs.