Erdős Problem #628 — The Erdős–Lovász–Tihany Conjecture

Let $G$ be a finite simple graph, and let $\omega(G)$ and $\chi(G)$ denote its clique number and chromatic number. For integers $s,t\ge 2$, call $G$ $(s,t)$-splittable if its vertex set can be partitioned into sets $S$ and $T$ such that

$$\chi(G[S])\ge s\quad\text{and}\quad \chi(G[T])\ge t.$$

Erdős–Lovász–Tihany Conjecture. If

$$\omega(G)<\chi(G)=s+t-1,$$

then $G$ is $(s,t)$-splittable.

The conjecture is a central problem concerning chromatic partitions of graphs. The supplied status evidence records that several cases have been proved, including $(2,2)$, $(2,3)$, $(3,3)$, $(2,4)$, $(3,4)$ and $(3,5)$; the general conjecture remains open.