A Note on (3,1)-Choosable Toroidal Graphs

Abstract

An $(L,d{)}^{\ast }$-coloring is a mapping $\varphi$ that assigns a color $\varphi (v)\in L(v)$ to each vertex $v\in V(G)$ such that at most $d$ neighbors of $v$ receive colore $\varphi (v)$. A graph is called $(m,d{)}^{\ast }$-choosable, if $G$ admits an $(L,d{)}^{\ast }$-coloring for every list assignment $L$ with $|L(v)|\ge m$ for all $v\in V(G)$. In this note, it is proved that every toroidal graph, which contains no adjacent triangles and contains no 6-cycles and $l$-cycles for some $l\in \{5,7\}$, is $(3,1{)}^{\ast }$-choosable.

7 pages