A -division of a graph is a partition of its vertex-set into sets such that no contains a largest clique of . A graph is -divisible if each of its induced subgraphs with at least one edge has a -division.
Conforti, Cornuéjols, Kapoor and Vuškovic designed a polynomial algorithm to recognize even-hole-free graphs.
Conjecture 2 (Hoàng). Every even-hole-free graph is 3-divisible.
Conjecture 3 (Hoàng). If is an even-hole-free graph then .
Hayward and Reed proposed the following.
Conjecture 4 (Hayward and Reed). An even-hole-free graph contains a vertex whose neighbourhood can be partitioned into two cliques.
Conjecture 4 implies Conjecture 3 which in turn implies Conjecture 2. Let be an even-hole-free graph. Conjecture 4 implies that each induced subgraph of has a vertex of degree at most , and therefore . Since any graph is -divisible, is 3-divisible.
Contributed by Chinh Hoang.
Back to the main index for Perfect Graphs.