SOLVED
This has been resolved in some other way than a proof or disproof.
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.
Let $z(S_n)$ be the maximum value of $\zeta(G)$ over all graphs $G$ which can be embedded on $S_n$, the orientable surface of genus $n$. Determine the growth rate of $z(S_n)$.
A problem of Erdős and Gimbel. Gimbel
[Gi86] proved that\[\frac{\sqrt{n}}{\log n}\ll z(S_n) \ll \sqrt{n}.\]Solved by Gimbel and Thomassen
[GiTh97], who proved\[z(S_n) \asymp \frac{\sqrt{n}}{\log n}.\]
View the LaTeX source
Additional thanks to: Raphael Steiner
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 #759, https://www.erdosproblems.com/759, accessed 2026-01-16
