Logo
All Random Solved Random Open
SOLVED
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].