Problem Statement
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$.
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$.
Categories:
Graph Theory
Progress
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$.
Source: erdosproblems.com/1111 | Last verified: January 19, 2026