Erdős–Lovász Tihany conjecture: disjoint subgraphs with $\chi\ge a$ and $\chi\ge b$ when $a+b=\chi+1$ (Erdős #628)
Statement
Let $G$ be a graph with chromatic number $\chi(G)=k$ that contains no complete subgraph $K_k$. If $a,b\geq 2$ are integers with $a+b=k+1$, must there exist two vertex-disjoint subgraphs of $G$ with chromatic numbers $\geq a$ and $\geq b$ respectively? A graph with this property for a given pair $(a,b)$ is called $(a,b)$-splittable, so the conjecture says: every $K_k$-free graph of chromatic number $k$ is $(a,b)$-splittable for every $a,b\ge 2$ with $a+b=k+1$. A counterexample would be a specific finite graph $G$ together with a pair $(a,b)$ for which no two vertex-disjoint induced subgraphs achieve chromatic numbers $a$ and $b$.
Acceptance. FULLY RESOLVES: (a) a counterexample — an explicit finite graph $G$ (adjacency data), its chromatic number $k$ certified by a proper $k$-coloring plus a machine-checkable non-$(k-1)$-colorability certificate (e.g., SAT UNSAT/DRAT proof), a certificate that $G$ has no $K_k$, a stated pair $(a,b)$ with $a,b\ge2$, $a+b=k+1$, and a reproducible exhaustive verification (it suffices to check all bipartitions of the vertex set) that no two vertex-disjoint subgraphs have chromatic numbers $\ge a$ and $\ge b$; or (b) a proof of the conjecture for all $k$ and all admissible $(a,b)$ — machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES: (a) a proof for new pairs $(a,b)$ or a new graph class strictly beyond the settled pairs and graph classes stated in the background; (b) machine-verified exhaustive confirmation that no counterexample on up to $n$ vertices exists for specific small $(k,a,b)$, with code and unsatisfiability certificates; (c) a proof of a weakened splitting statement for all graphs that strictly improves the best published partial result identified in the submission. Deliver the counterexample graph plus all certificates and checking code, or the proof file, or the search code with its exhaustiveness certificate and attained range.
Background
A question of Erdős and Lovász, published by Erdős in [Er68b] and universally known as the Erdős–Lovász Tihany conjecture; listed as open on erdosproblems.com/628 (fetched 2026-07-13, status 'falsifiable'). Erdős originally asked the case $a=b=3$ (i.e. $k=5$), which was proved by Brown and Jung [BrJu69] — they showed the stronger statement that such a graph must contain two vertex-disjoint odd cycles. For general graphs, the only settled pairs to date are $(a,b)\in\{(2,2),(2,3),(2,4),(3,3),(3,4),(3,5)\}$: $(2,2)$ is trivial, $(2,3)$ and $(3,3)$ are due to Brown and Jung, $(2,4)$ was proved independently by Mozhan and by Stiebitz (1987), and $(3,4)$, $(3,5)$ by Stiebitz. Balogh, Kostochka, Prince, and Stiebitz [BKPS09] proved the full conjecture (all admissible $(a,b)$) for quasi-line graphs and for graphs with independence number $2$. Further partial results are collected in Song's comprehensive survey of the problem [So22]; more recently, Longbrake and Tariq (arXiv:2406.15164, 2024) proved the conjecture for pairs $(a,b)$ with $b\le a+2$ whenever the graph contains a $K_a$, and for claw-free graphs containing a $K_a$ whenever $b\le 4a-3$. The problem also appears in the UCSD Erdős graph-problem collection under 'decompose to increase chromatic number'. Note the general shape: the conjecture claims chromatic number 'splits' additively (with one spare unit) in any graph that is critical enough to have no $K_k$; it is a cousin of double-critical-graph questions in the same literature. The attacker's tool: SAT/ILP encodings — chromatic number, $K_k$-freeness, and $(a,b)$-splittability of a candidate graph are all finitely checkable, so exhaustive small-order searches for counterexamples (with DRAT-style unsatisfiability certificates) and machine-verified confirmations for small $k$ are genuinely available, alongside structural proofs for new hereditary graph classes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #628 (T. F. Bloom) | website |
| REF-02 | Erdős graph problem collection (UCSD): Decompose to increase chromatic number | website |
| REF-03 | Z.-X. Song, The Erdős–Lovász Tihany Conjecture — a survey (2022) [So22] | paper |
| REF-04 | S. Longbrake, J. Tariq, Some Cases of the Erdős–Lovász Tihany Conjecture for Claw-free Graphs (arXiv:2406.15164) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.