Erdős problem 760

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 independent set.

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.