FALSIFIABLE
Open, but could be disproved with a finite counterexample.
Let $G$ be a graph with chromatic number $k$ containing no $K_k$. If $a,b\geq 2$ and $a+b=k+1$ then must there exist two disjoint subgraphs of $G$ with chromatic numbers $\geq a$ and $\geq b$ respectively?
This property is sometimes called being $(a,b)$-splittable. A question of Erdős and Lovász (often called the Erdős-Lovász Tihany conjecture). Erdős
[Er68b] originally asked about $a=b=3$ which was proved by Brown and Jung
[BrJu69] (who in fact prove that $G$ must contain two vertex disjoint odd cycles).
Balogh, Kostochka, Prince, and Stiebitz
[BKPS09] have proved the full conjecture for quasi-line graphs and graphs with independence number $2$.
For more partial results in this direction see the comprehensive survey of this problem by Song
[So22].
See also
the entry in the graphs problem collection.
View the LaTeX source
This page was last edited 06 December 2025.
Additional thanks to: Quanyu Tang
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #628, https://www.erdosproblems.com/628, accessed 2026-02-13
