On the divisibility of graphs

A graph G is k-divisible if for each induced subgraph H of G with at least one edge, there is a partition of the vertex set of H into sets V-1,...,V-k such that no V-i contains a maximum clique of H. We show that a claw-free graph is 2-divisible if and only if it does not contain an odd hole: we conjecture that this result is true for any graph, and present further conjectures relating 2-divisibility to the strong perfect graph conjecture. We also present related results involving the chromatic number and the stability number, with connections to Ramsey theory. () 2002 Elsevier Science B.V. All rights reserved.