2026/07/22 by Zi-Xia Song
Mathematics · #math.CO
Let s, t≥2 be integers. A graph G is (s,t)-splittable if V(G) can be partitioned into two sets S and T such that χ(G[S ]) ≥ s and χ(G[T ]) ≥ t. The Erdős-Lovász Tihany Conjecture from 1968 asserts that every graph G satisfying ω(G)<χ(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 ω(G)<χ(G)=s+t-1. We prove that if G does not contain C4 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.