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)$.

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.

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}.\]