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.