Vertex Coloring Of Planar Graphs

A proper k-coloring of G is an assignment of k colors 1,2,…,κsuch that no adjacent vertices receive the same color.If G has a properκ-coloring,then G is said to beκ-colorable.The chromatic number,denoted byχ(G),is the least non-negative integerκsuch that G isκ-colorable.We say that L is an assignment for the graph G if it assigns a list L(v) of possible colors to each vertex v of G.If G has a proper coloringπsuch thatπ(v)∈L(v)for all vertices v,then we say that G is L-colorable orπis an L-coloring of G.The graph G isκ-choosable if it is L-colorable for every assignment L satisfying |L(v)|≥κfor all vertices v.The list chro-matic number of G,is the smallest integerκsuch that G isκ-choosable.A proper vertex coloringπof a graph G=(V,E)is acyclic if G con-tains no bicolored cycle.The acyclic chromatic number,denoted byχ_a(G), of a graph G is the least integerκsuch that G has an acyclicκ-coloring. A graph G is acyclically L-list colorable if for a given list assignment L there is an acyclic coloringπof the vertices such thatπ(v)∈L(v).If G is acyclically L-list colorable for any list assignment with |L(v)|≥κfor all v∈V(G),then G is acyclicallyκ-choosable.The acyclic list chromatic number,denoted byχ_a^l(G),of a graph G is the smallest integerκsuch that G is acyclicallyκ-choosable.In 1976,Steinberg ^[1]conjectured that every planar graph without 4-cycles and 5-cycles is 3-colorable.In 2002,Borodin et al.^[2]first investigated the acyclically list coloring of planar graphs to prove that every planar graph is acyclically 7-choosable. They also put forward to the following challenging conjecture:every pla-nar graph is acyclically 5-choosable. In this master thesis,we aim at the above two conjectures,and investi-gate some coloring problem of planar graphs.In Chapter 1,we collect some basic notions used in the thesis and give a chief survey in this direction.Main results in the thesis are stated.In Chapter 2,we prove that:(1)each planar graph without {4,6,7,9}-cycles is 3-colorable;(2)each planar graph without {4,6,8}-cycles is 3-colorable.In Chapter 3,we obtain that:(1)each planar graph without 4-cycles is acyclically 6-choosable;(2)each planar graph without 4-cycles and without triangles at dis-tance less than 3 is acyclically 5-choosable.