| On-line list coloring of a graph is an online version of list coloring.The concept of on-line list coloring was introduced by Schauz[23]and Zhu[31]in 2009.Assume G is a graph and f is a mapping from V(G)to N.The f-painting game on G(is also called on-line list coloring game)is played by two players:Lister and Painter.Initially,each vertex v has f(v)tokens and is uncolored.In each round,Lister chooses a set M of uncolored vertices and removes one token from each chosen vertex.Painter colors an independent subset X of M.Lister wins if at the end of some round,there is an uncolored vertex with no more tokens left.Otherwise,at some round,all vertices are colored and Painter wins.We say G is f-paintable if Painter has a winning strategy in this game.The on-line list coloring number of G is denoted by χp(G),it is the minimum positive integer k such that G is k-paintable.Alon-Tarsi Theorem[1]is a powerful tool in the study of list coloring of graphs.Alon-Tarsi Theorem was extended to paintability by Schauz[23].Coloring of planar graphs is an active area of research in graph theory.One direction of research is motivated by Steinberg Conjecture[12]from 1976,which asserts that every planar graph with no cycles of length 4 and 5 is 3-colorable.In 1991,Erdos[20]determined the smallest k such that planar graphs without cycles of length 4,5,...,k are 3-colorable.Recently,Steinberg’s conjecture was refuted by Cohen-Addad,Hebdige,Kral[5].It remains an open problem whether every planar graph with no cycles of length 4,5,6 is 3-colorable.Analog to Erdos’ question,people want to determine the smallest integer l such that every planar graph with no cycles of length 4,5,...,l is 3-choosable.It was proved by Borodin et al.[2]that l≤ 9.It was recently proved by Dvorak and Postle[7]that every planar graph with no cycles of length 4,5,...,8 is 3-choosable.Lam,Xu,and Liu[16]proved that every planar graph contains no 4-cycle is 4-choosable;Wang and Lih[27]proved that every planar graph contains no 5-cycle is 4-choosable;Juvan and Mohar[14]proved that every planar graph contains no 6-cycle is 4-choosable.Besides forbidden cycles of certain lengths,one may also add condition on the minimum distance d(?)between any two triangles.Let g be the family of planar graphs without cycles of length 4,5,6 and with d(?)≥2.Assume that G∈g.Then a 7-face is adjacent to at most two 3-faces.Assume that f is a 7-face of G,and adjacent to two(3,3,3)-faces,the degree of vertices of fare at most 4.If f has exactly one vertex of degree 4,we say f is a poor face.If f has exactly two vertices of degree 4,we say f is a semi-poor face.If a poor face f and a semi-poor face g intersect at a 4-vertex or f and g are adjacent at a(3,4)-edge,then we say f∪g is a special configuration of G.Jin and Wei[13]proved that if a planar graph G ∈ g,containing no special 7-cycle as shown in Figure 1.1,then G is 3-choosable.In this thesis,we strengthened this result,by proving that if a planar graph G∈g,containing no special configurations,then G is 3-paintable.This result is proved in Chapter 2 by using Alon-Tarsi Theorem and discharging method.In Chapter 3,we prove that for k ∈｛3,4,5,6｝,planar graphs contain no cycles of length k are 4-paintable. |
