Acyclic Coloring And List Coloring Of Graphs

In this Ph.D.dissertation,we study acyclic coloring and list coloring of graphs.A proper k-vertex-coloring of a graph G is a mapping f:V(G)?{1,2,...,k} such that f(x)?f(y)for every edge xy ? E(G).The chromatic number of G,denoted by x(G),is the smallest integer k such that G has a proper k-vertex-coloring.An acyclic k-vertex-coloring of G is a proper k-vertex-coloring such that every cycle is colored with at least three colors.The acyclic chromatic number,denoted by ?a(G),of G is the smallest integer k such that G has an acyclic k-vertex-coloring.Similarly,we can define proper k-edge-coloring,chromatic index,denoted by ?'(G),acyclic k-edge-coloring,acyclic chromatic index,denoted by X'a(G).Assign a list assignment L to v? V(G).? is called an L-coloring of G if G has a coloring ? such that ?(?)? L(v)and ?(x)??(y)for xy ? E(G)A list k-coloring of G is an L-coloring for every assignment L satisfying |L(v)|?k for all vertices v ? V(G).G is also called list k-colorable or k-choosable.The list chromatic number or choice number of G,denoted by ?l(G),is the smallest positive integer k such that G is k-choosableA graph G is called 1-planar if it can be drawn in the plane so that every edge has at most one crossing.We say that two distinct crossings are independent if the end-vertices of any two pairs of crossing edges are disjoint.If all crossings in a 1-planar graph G are independent,then we say that G is an IC-planar graphIn 1965,Ringel conjectured that every 1-planar graph G is 6-colorable,and in 1995.Borodin verified this conjecture.In 2008,Albertson investigated vertex coloring of IC-planar graph,and conjectured that IC-planar graph is 5-colorable.Later,Kral confirmed this conjecture.In 1973,Grunbaum proposed the concept of the acyclic vertex coloring,and conjectured that every planar graph G is acyclically 5-colorable.In 1979,Borodin proved this conjecture.In 2001,Borodin et al.proved that every 1-planar graph G has ?a(G)?20.In 1991,Alon confirmed that every graph G satisfies c?4/3/(log?)1/3??a(G)?50?4/3,where c is constant and ? is sufficiently large.In 1978,Fiamcik introduced the concept of the acyclic edge coloring,and put forward a conjecture that every simple graph G has ?'a(G)??+2.In 2019,Fialho et al.applied Lovasz Local Lemma to prove that every simple G has ?'a(G)?[3.569(?-1)].Let G be a 1-planar graph without 3-cycle.Song and Miao verified that ?'a(G)??+22.Chen et al.improved this upper bound to ?+16.In 1979,Erdos et al.conjectured that every planar graph G is 5-choosable.Thomassen proved this conjecture in 1994In this Ph.D.dissertation,we study acyclic coloring and list coloring of IC-planar graphs and 1-planar graphs.This dissertation consists of four chapters as followsIn Chapter 1,we collect some concepts and notation used in the dissertation.Re-search progress on the acyclic coloring and list coloring of graphs are surveyed.Main results obtained in the dissertation are statedIn Chapter 2,we investigate the acyclic vertex coloring of IC-planar graphs and 1-planar graphs,respectively.Then the following results are shown(1)Let G be an IC-planar graph and G*be its correlative planar graph.Then Xa(G)<2Xa(G*)(2)Let G be an IC-planar graph.Then(i)?a(G)<10(ii)If moreover g(G)>9,then ?a(G)?8(iii)If moreover g(G)>13,then ?a(G)?6(3)Let G be a 1-planar graph,then ?a(G)?18In Chapter 3,we study the acyclic edge coloring of 1-planar graphs and 1-planar graphs without special cycles by showing the following three results(1)If G is a 1-planar graph,then ?'a(G)??+36(2)If G is a 1-planar graph without 4-cycle,then ?'a(G)??+22(3)If G is a 1-planar graph without 3-cycle,then ?'a(G)??+14In Chapter 4,we focus on the list coloring of IC-planar graphs,and prove that every IC-planar graph G has ?l(G)?6.