Some Coloring Problems Of Planar Graphs And 1-planar Graphs

Graph coloring is a classical and active field in graph theory.Graph coloring problems have developed from traditional colorings,such as edge colorings,vertex colorings and total colorings,to much more new-type colorings,each of which has its important theoretical value and appropriate applicable background.Many variants of graph colorings have wide-ranging applications in algorithm design,scheduling and resource allocation,which not only motivate the study of many interesting open questions but also motivate the development of new and innovative methods.All of the above have greatly enriched the graph coloring theory.In this paper,we will mainly study acyclic list(vertex)colorings,proper edge colorings,proper total colorings,(p,1)-total colorings and adjacent vertex distinguishing total colorings of planar graphs and 1-planar graphs.All graphs considered here are finite,undirected,simple and nonempty.For a graph G,we use V(G),E(G),?(G)to denote the vertex set,the edge set and the maximum degree of G,respectively.Let v(G)= |V(G)| and e(G)= |E(G)| denote the order and size of G,respectively.The girth of a graph G is the length of the shortest cycle in G,which is denoted by g(G).A cycle is called triangular(resp.quadrangular)if it is adjacent to a 3-cycle(resp.4-cycle)other than itself.A graph which can be drawn in the plane in such a way that edges meet only at points corresponding to their common ends is called a planar graph,and such a drawing is called a planar embedding of the graph.A planar embedding is often referred as a plane graph.A graph is a 1-planar graph if it can be drawn in the plane so that each edge is crossed by at most one other edge,such a drawing is called a 1-planar embedding,which is also called its 1-plane graph.For each crossing vertex ? in a 1-plane graph,w is corresponding to two crossing edges which create w and a vertex set ?(w)of four endpoints of the two crossing edges.A 1-planar graph G is said to be an IC-planar graph if ?(?)??(?)=(?)for any two crossing vertices ? and w'in a 1-plane graph of G.A proper k-coloring of a graph G is a mapping ?:V(G)?{1,2,...,k} such that ?(x)??(y)for any two adjacent vertices x and y in G.The minimum k such that G has a proper k-coloring is called the chromatic number,denoted by ?(G).A proper coloring of a graph G is acyclic if every cycle in G has at least three colors.L = {L(v):v ?V(G)} is called an assignment for a graph G if it assigns a list L(v)of possible colors to each vertex v of G.For a given list assignment L,a graph G is acyclically L-list colorable if there is an acyclic coloring 0 of G such that?(v)?L(v)for all v ?V(G).A graph G is acyclically k-choosable if G is acyclically L-list colorable for any list assignment with |L(v)|?k for all v ?V(G).The acyclic list chromatic number of G,denoted by ?al(G),is the smallest integer k such that G is acyclically k-choosable.Borodin et al.conjectured that every planar graph is acyclically 5-choosable.We discuss the sufficient conditions for acyclic 5-choosability or acyclic 6-choosability of planar graphs which allows adjacent triangles.A proper edge k-coloring of a graph G is a mapping ?:E(G)?{1,2,…,k}such that ?(x)? ?(y)for any two adjacent edges x and y in G.The minimum k such that G has a proper edge k-coloring is the chromatic index,denoted by ?'(G).Vizing's theorem tells us that ?'(G)= ?(G)or ?(G)+1 for every simple graph G.This theorem divides all graphs into two classes:a graph G is said to be of Class one if ?'(G)= ?(G),and of Class two if ?'(G)= ?(G)+ 1.A connected graph G is critical if G is of Class Two and ?'(G-e)<?'(G)for every edge e?E(G).A critical graph G with maximum degree ? is said to be ?-critical.Zhang and Wu proved that every 1-planar graph G with ?(G)>10 is of Class 1.Later,Zhang and Liu constructed 1-planar graphs of Class 2 with maximum degree 6 or 7 and conjectured that every 1-planar graph with ?(G)?8 is of Class 1.We prove that under the constraints of chordal cycles,a graph G is of Class 1 if G is either a special 1-planar graph with ?(G)?8 or a special IC-planar graph with ?(G)?7.A proper total k-coloring of a graph G is a mapping ?:V(G)U E(G)?{1,2,…,k} such that no two adjacent or incident elements receive the same color.The minimum k such that G has a proper total k-coloring is called the total chro-matic number,denoted by ?"(G).Behzad and Vizing independently proposed the Total Coloring Conjecture:?"(G)??(G)+ 2 for every graph G.By the structural constraints of 1-planar graphs,we determine the upper bounds of total chromatic numbers of 1-planar graphs with the maximum degree at least 9 and 12,respectively.A k-(p,1)-total labelling of a graph G is a mapping ? from V(G)U E(G)to the color set {0,1,…,k} such that |?(u)-?(v)|?1 if uv?E(G),|?(e1)-?(e2)|?1 if e1 and e2 are two adjacent edges in G and |?(u)-?(e)|?p if the vertex u is incident with the edge e.The minimum k such that G has a k-(p,1)-total labelling,denoted by ?pT((G),is called the(p,1)-total labelling number of G.Havet and Yu proposed the(p,l)-Total Labelling Conjecture:?pT(G)?min{A(G)+ 2p-1,2?(G)+p-1}for any graph G.We obtain the upper bound of ?pT(G)if G is either a planar graph with ?(G)?4p + 4 or a special 1-planar graph with ?(G)?6p + 3.In a proper total k-coloring ? of a graph G,let C?(v)denote the set of colors of the edges incident with v and the color of v.If for each edge uv ?E(G),C?(u)?C?(v),then we call such a proper total k-coloring an adjacent vertex distinguishing total k-coloring of G.The minimum k in such a coloring is called the adjacent vertex distinguishing total chromatic number of G,denoted by ?a"(G).Zhang et al.conjectured the following:?a"(G)??(G)+ 3 for any graph G with order at least two.We will use an algebraic tool "Combinatorial Nullstellensatz" to analyze the configurations of a graph,and obtain that the conjecture above is true for some special planar graphs with maximum degree at least 8.In order to clearly state our results,we divide this paper into five chapters.In Chapter 1,we firstly introduce basic notations and definitions.Then we describe the basic structures of graphs involved,and we state the definitions of relative colorings and their conjectures along with the recent developments.Finally,we give a list of our results.In Chapter 2,we discuss the acyclic list(vertex)colorings of planar graphs.We focus on the configurations by local adjustment of colors of certain vertices.We prove that for a planar graph G without 5-cycles and adjacent 4-cycles,G is acyclically 5-choosable if every vertex in G is incident with at most one j-cycle,j?{6,7}.Moreover,we prove that a planar graph G is acyclically 6-choosable if G contains neither triangular 5-cycles nor quadrangular k-cycles,k ?{4,5}.In Chapters 3,we study the edge colorings of 1-planar graphs.By observing and analyzing the structures of ?-critical graphs,we obtain the following two results.For a 1-planar graph G with ?(G)?8,G is of Class 1 if every 5-cycle in G contains at most one chord;for an IC-planar graph G with ?(G)>7,G is of Class 1 if G contains no adjacent chordal 6-cycles.In Chapter 4,we discuss proper total colorings,(p,1)-total colorings and ad-jacent vertex distinguishing total colorings of planar graphs and 1-planar graphs.Firstly,as to proper total colorings,by analyzing the structural properties of 1-planar graphs with girth constraints,we obtain the following results:if G is a 1-planar graph with ?(G)? 9 and g(G)?4,then ?"(G)??(G)+ 2;if G is a 1-planar graph with ?(G)?12 and g(G)?5,then ?"(G)??(G)+ 1.Secondly,we get some results in(p,1)-total coloring with p?2.If G is either a planar graph with ?(G)?4p + 4 or a 1-planar graph with ?(G)?6p + 3 which has no adjacent triangles,then ?pT(G)??(G)+ 2p-2.Finally,we prove that ?a"(G)??(G)+ 3 for every planar graph G with ?(G)?8 and without adjacent 4-cycles.In Chapter 5,we propose some problems at the present stage and give some feasible methods for further research.