The Choice Number Versus the Chromatic Number for Graphs Embeddable on Orientable Surfaces

  • Brahadeesh Sankarnarayanan
  • Niranjan Balachandran

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

Published
2021-12-17
Article Number
P4.50