Toroidal graphs without $K_5^{-}$ and 6-cycles

Abstract

Cai et al.\ proved that a toroidal graph $G$ without $6$-cycles is $5$-choosable, and proposed the conjecture that $\text{ch}(G)=5$ if and only if $G$ contains a $K_5$ [J. Graph Theory 65 (2010) 1--15], where $\text{ch}(G)$ is the choice number of $G$. However, Choi later disproved this conjecture, and proved that toroidal graphs without $K_5^{-}$ (a $K_5$ missing one edge) and $6$-cycles are $4$-choosable [J. Graph Theory 85 (2017) 172--186]. In this paper, we provide a structural description, for toroidal graphs without $K_5^{-}$ and $6$-cycles. Using this structural description, we strengthen Choi's result in two ways: (I) we prove that such graphs have weak degeneracy at most three (nearly $3$-degenerate), and hence their DP-paint numbers and DP-chromatic numbers are at most four; (II) we prove that such graphs have Alon-Tarsi numbers at most $4$. Furthermore, all of our results are sharp in some sense.

15pages, 7 figures