Erdős–Lovász Tihany conjecture

Color five dots joined in a ring, with neighboring dots given different colors. Three colors are needed even though no three dots are all joined to each other. Split off two neighboring dots: they need two colors, and the remaining three-dot path also needs two. Does such a split exist for every requested pair of color counts, each at least two and adding up to one more than the whole graph’s count, whenever that count exceeds its largest fully joined group?[1]

Can a graph’s coloring requirement be retained in two disjoint pieces even when it comes from more than a large fully joined group? On the five-cycle A–B–C–D–E–A, the parts {A,B} and {C,D,E} each contain an edge and need two colors. The whole cycle needs three, while its largest clique has two vertices.

The chromatic number $\chi(G)$ is the fewest colors needed; the clique number $\omega(G)$ is the largest fully joined group. For a finite simple graph and integers $s,t\geq2$, assume $\omega(G)<\chi(G)=s+t-1$. Must its vertices partition into S and T with $\chi(G[S])\geq s$ and $\chi(G[T])\geq t$? Here an induced subgraph keeps exactly the vertices in its part and every edge between them.[1]

The small two-colors-per-part case is known. A July 2026 preprint reports the guarantee for graphs without certain even loops. These results do not cover every graph and every allowed pair of color requirements.[1]

The even-hole-free result is a preprint claim; the full graph target remains open.[1]

A fully joined group forces many colors at one dense spot. A ring can force an extra color through links spread around the graph. Distinguishing these sources of coloring constraints helps explain what a global color count tells us about a graph’s internal structure.[1]

A triangle illustrates why the clique condition matters: it needs three colors, but splitting its three vertices leaves a part with only one vertex, so both parts cannot need two colors. The five-cycle has the same total color requirement without that concentrated obstruction. Comparing the two shows why clique number and chromatic number carry different structural information, and why induced parts are a way to examine the difference.[1]