Acyclic Choosability Of Planar Graphs

Let G be a finite and simple graph.For a graph G,we use V(G)and E(G)to denote its vertex set and edge set,respectively.A proper k-coloring of a graph G is an assignment 7r:V→{1,2,…,k} such that for any edge xy ∈ E,we have that π(x)≠π(y).We say that G is k-colorable.The chromatic number,denoted by x(G),of a graph G is the smallest positive integer k such that G has a k-coloring.A proper vertex coloring of a graph is acyclic if there is no bicolored cycle in G.That is,every cycle uses at least three colors.The acyclic chromatic number of a graph G,denoted by Xa(G),is the smallest positive integer k such that G has an acyclic k-coloring.Acyclic coloring of graphs was firstly introduced by Grunbaum in 1973.In the meantime,he proved that every planar graph is acyclically 9-colorable.Moreover,he conjectured that every planar graph is acyclically 5-colorable,which was later confirmed by Borodin.For each vertex v of G,we assign a list L(v)of possible colors to it,where L ={L(v)| v ∈ V}.If G has a proper coloring π such that π(v)∈ L(v)for each vertex v,then we say that G is L-colorable or π is said to be an L-coloring of G.The graph G is k-choosable if it is L-colorable for every assignment L satisfying that |L(v)| = k for all vertices v ∈V(G).We call that the list chromatic number of G,denoted by xl(G),is defined to be the smallest positive integer k such that G is k-choosable.If there is an acyclic coloring π of the vertices such that π(v)∈ L(v)for every vertex v,then we say G is acyclically L-colorable.Meanwhile,the coloring π is called an acyclic L-coloring of G.Similarly,if G is acyclically L-colorable with |L(v)| = k,then G is acyclically k-choosable.The acyclic choosability of G,denoted by Xal(G),is the smallest positive integerk such that G is acyclically k-choosable.In 2002,Borodin,Fon-Der Flaass,Kostochka,Raspaud and Sopena first proposed and investigated acyclic list coloring of planar graphs.They proved that every planar graph is acyclically 7-choosable.Moreover,they posed the following challenging conjec-ture:every planar graph is acyclically 5-choosable.By forbidding the cycles of length 4,in 2002,Montassier,Raspaud and Wang conjectured that every planar graph without 4-cycles is acyclically 4-choosable.However,as far as we know,these two conjectures still remain open.Recently,the research of acyclic 4-choosability of planar graphs attracts much more attention around the world.In this master thesis,we shall investigate this problem and give several sufficient conditions for planar graphs to be acyclically 4-choosable.The framework is shown as follows:In Chapter 2,Chapter 3 and Chapter 4,we shall make use of contradiction to show that the minimal counterexample cannot exist.The main methods are the coloring extension and the classical discharing.More precisely,we shall prove the following three results.(1)Every planar graph without intersecting 5--cycles is acyclic 4-choosable.(2)Every planar graph without 4-cycles,intersecting 3-cycles and intersecting 5-cycles is acyclic 4-choosable.(3)Every planar graph without 4-,7-and 9-cycles is acyclic 4-choosable.