A Lebesgue's type theorem on toroidal graphs and its application to linear coloring
Xiaoyan Zhang, YiAn XU · Scientia Sinica Mathematica · 2011
A coloring of a graph G is said to be linear if any two color classes induce an acyclic subgraph of maximum degree at most 2. In this paper, we first prove a Lebesgue's type theorem concerning the structure of toroidal graphs. As a consequence of this result, we show that every toroidal graph G of girth at least 5 can be 「(△(G))/2」+ 4)-linear list colorable, unless △(G) = 4 and G has a subgraph containing only faces of degree five of which each is incident with three vertices of degree 3 and two vertices of degree 4. This generalizes and improves some known results.