Even-Hole-Free Graphs

A $k$-division of a graph $G$ is a partition of its vertex-set into sets $V_1, \ldots, V_k$ such that no $V_i$ contains a largest clique of $G$. A graph is $k$-divisible if each of its induced subgraphs with at least one edge has a $k$-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 $G$ is an even-hole-free graph then $\chi (G) \leq 2 \omega (G) -1$.

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 $G$ be an even-hole-free graph. Conjecture 4 implies that each induced subgraph $H$ of $G$ has a vertex of degree at most $2 \omega(H) - 2$, and therefore $\chi (G) \leq 2 \omega (G) -1$. Since any graph $F$ is $\frac{\chi(F)}{\omega(F) -1}$-divisible, $G$ is 3-divisible.

Contributed by Chinh Hoang.

Back to the main index for Perfect Graphs.