Erdős #1111 · graph theory

A problem of El Zahar and Erdős [ElEr85], who show that it suffices to consider the case $t\leq c$. Let $d(t,c)$ be the minimal such $d$.

El Zahar and Erdős note that a result of Wagon [Wa80b] implies $d(t,2)\leq \binom{t}{2}+1$ (and in fact $d(t+1,2)\leq d(t,2)+t$). We also have $t(2,2)=2$ and $t(3,2)=4$ and $t(4,2)=5$.

El Zahar and Erdős proved $d(3,3)\leq 8$ and

for $t>3$.

Nguyen, Scott, and Seymour [NSS24] prove that if $t,c\geq 1$ then there exists $d\geq 1$ such that if $\chi(G)\geq d$ and $\omega(G)<t$ then there are anticomplete sets $A,B$ with $\chi(B)\geq c$ and such that the minimum degree of the induced graph on $A$ is at least $c$.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.