\((3,2)^*\)-Choosability of Triangle-Free Toroidal Graphs

Abstract

A list-assignment \(L\) to the vertices of \(G\) is an assignment of a set \(L(v)\) of colors to vertex \(v\) for every \(v \in V(G)\). An \((L,d)^*\)-coloring is a mapping \(\phi\) that assigns a color \(\phi(v) \in L(v)\) to each vertex \(v \in V(G)\) such that at most \(d\) neighbors of \(v\) receive color \(\phi(v)\). A graph is called \((k,d)^*\)-choosable, if \(G\) admits an \((L,d)^*\)-coloring for every list assignment \(L\) with \(|L(v)| \geq k\) for all \(v \in V(G)\). In this note, it is proved that:(1) every toroidal graph containing neither adjacent \(3\)-cycles nor \(5\)-cycles, is \((3,2)^*\)-choosable;(2) every toroidal graph without \(3\)-cycles, is \((3,2)^*\)-choosable.