Problem 1111

Erdős Problem #1111: declared status 'open'. Formalized: no. 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$. Current best: A problem of El Zahar and Erd\H{o}s [ElEr85], who show that it suffices to consider the case $t\leq c$. 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$. Prize: no. Tags: graph theory.