The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs
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 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.
The paper establishes the Erdős–Lovász Tihany conjecture for all even-hole-free graphs, producing vertex partitions whose induced subgraphs retain prescribed chromatic numbers — extending a difficult chromatic partition conjecture to a substantial hereditary graph class.
Reproduction
✓* reproduced, conditional on declared hypotheses
Attempted: For every finite simple graph G and integers s, t ≥ 2, assuming the Chudnovsky–Seymour theorem that every nonempty finite even-hole-free graph has a bisimplicial vertex: if G is even-hole-free and ω(G) < χ(G) = s + t − 1, then G is (s,t)-splittable. The paper's new Theorem 1.4 is proved outright, with no hypothesis.
A single self-contained development with zero sorry and no custom axioms; the one declared hypothesis is a cited prior landmark (Chudnovsky–Seymour), isolated as an explicit statement and used only where the paper itself invokes it. One erratum found and repaired: the paper chooses |A| ≤ |B| where its own argument requires |B| ≤ |A|; the corrected choice completes the proof and is documented in the run's README. Independent re-verification: elaborates cleanly, kernel-checked, standard axioms only; the hypothesis structure was audited directly.
trace (196 events) · code (2 files)