PROVED
This has been solved in the affirmative.
The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph.
If $G$ is a graph with chromatic number $\chi(G)=m$ then must $G$ contain a subgraph $H$ with\[\zeta(H) \gg \frac{m}{\log m}?\]
A problem of Erdős and Gimbel, who proved that there must exist a subgraph $H$ with\[\zeta(H) \gg \left(\frac{m}{\log m}\right)^{1/2}.\]The proposed bound would be best possible, as shown by taking $G$ to be a complete graph.
The answer is yes, proved by Alon, Krivelevich, and Sudakov
[AKS97].
View the LaTeX source
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 #760, https://www.erdosproblems.com/760, accessed 2026-02-13
