OPEN
This is open, and cannot be resolved with a finite computation.
If $G$ is a finite graph and $A,B$ are disjoint sets of vertices then we call $A,B$ anticomplete if there are no edges between $A$ and $B$.
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(A)\geq \chi(B)\geq c$.
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\[d(t,3) \leq 2\binom{t-1}{3}+7\binom{t-1}{2}+t\]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$.
View the LaTeX source
This page was last edited 07 December 2025.
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 #1111, https://www.erdosproblems.com/1111, accessed 2026-02-13
