Acyclic Choosability Of Planar Graphs

A proper k-coloring of a graph G is a mapping (?):V(G)â†'{1,2,…, k}, such that no adjacent vertices receives same colors. If G has a proper k-coloring, then G is said to be k-colorable. The chromatic number, denoted by χ(G), is the least non-negative integer k such that G is k-colorable.A coloring Ï€ is acyclic if Ï€ is a proper vertex coloring of G such that any cycle subgraph has at least3colors, The acyclic chromatic number, denoted by Xa(G), is the least non-negative integer k such that G is acyclic k-coloring. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring Ï€ of G such that Ï€(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with|L(v)|≥k for all v∈V, then G is acyclically k-choosable. The acyclic list chromatic number, denoted by χla{G),is the least non-negative integer k such that G is acyclic k-choosable.In2002,Borodin, Fon-Der Flass, Kostochka, Raspaud and Sopena proved that every planar graph is acyclically7-choosable. They also put forward the following challenging conjecture:Every planar graph is acyclically5-choosable. However, this conjecture is still open. Around this conjecture, Montassier, Raspaud and Wang posed the other conjecture:Every planar graph without4-cycles is acyclically4-choosable. Unfortunately this conjecture is also still open.In this master thesis, we aim at the above two conjectures, and investigate the acyclic vertex list coloring of planar graphs. The thesis consists of three chapters.In Chapter1, we introduce some basic notions and give a chief survey in this direc-tion.In Chapter2, we prove that every planar graph G is acyclically6-choosable if G does not contain4-cycles adjacent to z-cycles for each i∈{3,4,5,6}.In Chapter3, we prove that:(1) Planar graphs without4-cycles, adjacent5-cycles, adjacent3-cycles and6-cycles are acyclically4-choosable.(2) Let G be a planar graph. If d(Ci,Gj>≥1, then χla(G)≤4, where3≤i, j≤5, Cs a cycle of length i.