4-Choosability Of Toroidal Graphs Without 4-Cycles

For each vertex v in a graph G, let l(v) denote a list of colors available at v. A list coloring or choice function is a proper coloring f such that f(v)∈L(v) for all v. A graph G is k-choosable or list k-colorable if every assignment of k-element lists to the vertices permits a proper list coloring. The list chromatic number, choice number, or choosability x(?)(G) is the minimum k such that G is k-choosable.The surface is closed if it has no boundary and can be subdivided into finite polygons. The sphere is the simplest closed surface. The genus of a surface obtained by adding handles to a sphere is the number of handles added; we use S_γfor the surface of genusγ. The genus of a graph G is the minimumγsuch that G embeds on S_γThe graphs, whose genuses are 0, 1, are called the planar and toroidal graphs, respectively.In [18] , the authors proved the 4-choosability of plane graphs without 4-cycles, based on which we prove in this paper:Theorem : Toroidal graphs without 4—cycles are 4—choosable.