Choice number of embedded graphs For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number $\chi(g)$ and maximal choice number $cn(g)$. Famous results are $\alpha(g)=\chi(g)=[(7+\sqrt{1+48g})/2]$ for all $g$ (Heawood conjecture), and $cn(0)=5$ (upper bound due to Thomassen). What is known for values of $cn(g)$ with $g>0$?
 A: I will use the Euler genus, so that I can also talk about non-orientable surfaces.  The Euler genus of a sphere with $g$ handles is $2g$ and the Euler genus of a sphere with $g$ crosscaps is $g$.
The maximal choice number for a surface of Euler genus $\epsilon$ turns out to be almost always equal to the Heawood Bound 
$$H(\epsilon)=\left\lfloor \frac{7+\sqrt{24\epsilon+1}}{2} \right\rfloor.
$$
  The following theorem due to Böhme, Mohar, and Stiebitz settles everything. 
Theorem. Let $\Sigma$ be a surface of Euler genus $\epsilon$ with $\epsilon \geq 1$ and $\epsilon \neq 3$. If
$G$ is a graph embedded on $\Sigma$, then the choice number of $G$ is at most $H(\epsilon)$ where equality holds if and
only if $G$ contains a complete subgraph on $H(\epsilon)$ vertices. 
As noted by Fedor, the maximum choice number of a graph embedded on the sphere is $5$ (instead of $H(0)=4$).  
As with the chromatic number, the Klein bottle is also exceptional.  The maximum choice number is $6$ (instead of $H(2)=7$). 
