Erdős Problems

Tags Prizes

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

#759: [ErGi93]

graph theory, chromatic number

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

Additional thanks to: Raphael Steiner