List Coloring Of Toroidal Graphs

All graphs considered in this paper are finite, simple and undirected. A toroidal graph G is a graph drawn on the torus without crossing edges. The proper list coloring of G means:a list assignment L of G assigns a list L(v) of available colors for every v ∈ V(G). A k-list assignment satisfies that |L(v)|≥ k for any vertex v. An L-coloringφ of a graph G is a coloring of G such that φ(v) ∈ L(v) for every v ∈ V(G), and φ(x)≠φ(y) whenever xy ∈ E(G). G is L-colorable if it admits an L-coloring. Call G k-choosable if it is L-colorable for every k-list assignment L.The improper list coloring of G means:let d be a non-negative integer. An (L, d)*-coloring is a mapping φ that assigns a color φ(v) ∈ L(v) to each vertex v ∈ V(G) such that at most d neighbors of v receive colorφ(v). A graph G is called (k, d)*-choosable if it admits an (L,d)*-coloring for every list assignment L with |L(v)|≥ k for all v ∈ V(G).So proper list coloring is a special case of improper list coloring and improper list coloring is an extension of proper list coloring.A proper vertex coloring φ of a graph G is star coloring if the union of any pair of color classes induces a star forest. G is L-star-colorable if for a given list assignment L there is a star-coloring φ such that φ(v) ∈ L(v). If G is L-star-choosable for any list assignment with |L(v)|> k for all v ∈ V(G), then G is k-star-choosable.There have been many results by many researchers on k-choosability and (k, d)*-choosability. They also consider whether these results are true on toroidal graphs. Around the question, people made related research and gained a series of achievements.This master thesis, consisting of four chapters, focuses on this question, we make some improvement on several previous results. In the first chapter, we introduce some definitions and give a brief survey of proper list coloring and improper list coloring. In the second chapter, we introduce that toroidal graphs without cycles of length 4 and i for every i ∈{5,7,8} are (3, 1)*-choosable. In the third chapter, we introduce that toroidal graphs without cycles of length 4, i,j which (i,j) ∈{(5,7), (6,8)} and the distance of triangles is at least 3 are 3-choosable. In the forth chapter, we introduce that every toroidal subcubic graph is 6-star-choosable.