The choice number versus the chromatic number for graphs embeddable on orientable surfaces

Abstract

We show that for loopless $6$-regular triangulations on the torus the gap between the choice number and chromatic number is at most $2$. We also show that the largest gap for graphs embeddable in an orientable surface of genus $g$ is of the order $\Theta (\sqrt{g})$, and moreover for graphs with chromatic number of the order $o(\sqrt{g}/{\log }_2(g))$ the largest gap is of the order $o(\sqrt{g})$.

arXiv comment17 pages, 6 figures; changed notation of the triangulations to T(r, s, t) from T(s, r, t), added a reference in the last section, corrected typos

References in corpus (1)

• $5$-list-coloring toroidal $6$-regular triangulations in linear time

Cited by in corpus (1)

• Note on $4$-coloring $6$-regular triangulations on the torus