The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs

Abstract

Let $s,t\ge 2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $\chi (G[S])\ge s$ and $\chi (G[T])\ge t$. The Erdős-Lovász Tihany Conjecture from 1968 asserts that every graph $G$ satisfying $\omega (G)<\chi (G)=s+t-1$ is $(s,t)$-splittable. A vertex of a graph is bisimplicial if the set of its neighbors can be expressed as the union of two cliques. Let $G$ be a graph with $\omega (G)<\chi (G)=s+t-1$. We prove that if $G$ does not contain $C_4$ as an induced subgraph and every induced subgraph of $G$ has a bisimplicial vertex, then $G$ is $(s,t)$-splittable. Combining our result with a recent result of Chudnovsky and Seymour, which states that every non-empty even-hole-free graph has a bisimplicial vertex, we obtain that the Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs.