Must large chromatic number with no K_t force two anticomplete c-chromatic subgraphs? (Erdős #1111)
Statement
For a finite graph $G$, let $\chi(G)$ be its chromatic number and $\omega(G)$ its clique number (largest number of pairwise adjacent vertices); for a vertex set $S$, $\chi(S)$ is the chromatic number of the induced subgraph $G[S]$. Two disjoint vertex sets $A,B$ are anticomplete if there is no edge between them. Conjecture (El Zahar–Erdős): for all integers $t,c\geq 1$ there exists $d\geq 1$ such that every graph $G$ with $\chi(G)\geq d$ and $\omega(G)<t$ contains anticomplete sets $A,B$ with $\chi(A)\geq\chi(B)\geq c$. Prove or disprove this, and estimate the least valid $d=d(t,c)$.
Acceptance. FULLY RESOLVES: prove the conjecture in full — for all $t,c$ the constant $d(t,c)$ exists (ideally with an explicit bound) — OR disprove it by exhibiting, for some $t,c$, graphs of arbitrarily large chromatic number with $\omega<t$ having no two anticomplete sets both of chromatic number $\geq c$. Complete proof (Lean/Coq preferred, otherwise a full written proof). ADVANCES, any of: (a) prove existence of $d(t,c)$ in the first open regime $c=4$ (any $t$), with proof; (b) determine a new exact value of $d(t,c)$ beyond the known $d(2,2)=2$, $d(3,2)=4$, $d(4,2)=5$, $d(3,3)\leq 8$, delivering an extremal $K_t$-free graph with $\chi=d(t,c)-1$ and no two anticomplete $c$-chromatic parts (machine-checkable) plus a certificate that the value is tight; (c) improve any upper bound on $d(t,c)$ stated in the background, strictly better than the best bound stated above, with proof; (d) strengthen the Nguyen–Scott–Seymour min-degree result toward the full $\chi(A)\geq c$ conclusion. Deliver the proof, or the extremal graph + verification/exhaustiveness certificate.
Background
A problem of El Zahar and Erdős [ElEr85], [Er85b], a landmark question in the Scott–Seymour $\chi$-boundedness program. They showed it suffices to treat $t\leq c$; write $d(t,c)$ for the minimal valid $d$. A result of Wagon [Wa80b] implies $d(t,2)\leq \binom{t}{2}+1$ (and $d(t+1,2)\leq d(t,2)+t$), with exact small values $d(2,2)=2$, $d(3,2)=4$, $d(4,2)=5$. El Zahar and Erdős proved $d(3,3)\leq 8$ and $$d(t,3)\leq 2\binom{t-1}{3}+7\binom{t-1}{2}+t\quad (t>3).$$ Thus the cases $c=2$ and $c=3$ are settled, but the conjecture is open for $c\geq 4$. Nguyen, Scott and Seymour [NSS24] proved a related weakening: for all $t,c\geq 1$ there is $d$ such that $\chi(G)\geq d$ and $\omega(G)<t$ force anticomplete $A,B$ with $\chi(B)\geq c$ and the induced subgraph on $A$ having minimum degree at least $c$ (minimum degree in place of $\chi(A)\geq c$). Listed as open on erdosproblems.com/1111 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Closely related to — but distinct from — the venue's Erdős–Lovász Tihany conjecture (Erdős #628), which partitions all vertices into two parts of prescribed chromatic numbers with no anticomplete requirement; here the two parts must be anticomplete and need not cover $G$. Attacker's tool: exhaustive / SAT search over $K_t$-free graphs of given chromatic number to compute exact $d(t,c)$ values and produce extremal witnesses.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1111 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.