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.