Problem Statement
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}?\]
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}?\]
Categories:
Graph Theory Chromatic Number
Progress
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].
Source: erdosproblems.com/760 | Last verified: January 16, 2026