Adjacent Vertex Distinguishing Total Coloring And Local Antimagic Labeling Of Graphs

Graph coloring and labeling are important branches in Graph Theory,and they have a long history.Four Color Theorem,as one of origins of Graph Theory,is a classical graph coloring problem.Graph coloring and labeling have attracted much attention all the time.They play an important role not only in Graph Theory but also in the social science,the biological science and so on.Essentially,graph coloring and labeling are mappings from the vertex set or edge set of graphs to the set of real numbers.Firstly,we study adjacent vertex distinguishing total coloring of planar graphs.The total-k-coloring of a graph G is to color the vertices and edges with colors(i.e.,elements)in the set[k]at the same time,such that any two adjacent elements and incident elements in V(G)∪ E(G)receive different colors.For a total-k-coloring φ of a graph G,let Cφ(v)={φ(v)}∪{φ(e)|e is incident to v}.We say that two adjacent vertices v and u are conflict,if Cφ(v)= Cφ(u).If any two adjacent vertices in G are not conflict,then we call the total-k-coloring φ adjacent vertex distinguishing(for short,AVD).We denote min{k | G has an AVD total-k-coloring} by χ"a(G).In 2005,Zhang et al.firstly introduced it and conjectured that χ"a(G)≤ △(G)+ 3 for any connected graph G with at least two vertices.Cheng et al.proved that planar graphs with maximum degree at least 10 fulfill the conjecture.In Chapter 2,we prove that χ"a(G)≤ △(G)+ 3 for any planar graph G with maximum degree △(G)≥ 9,which improves existing results and pushes the solution of the conjecture.In Chapter 3,we mainly consider local k-antimagic orientation of graphs.Suppose that D is an orientation of G and |E(G)|=m,a local k-antimagic labeling of D is an injective mapping from the edge set of D to[m + k],such that any two adjacent vertices have different vertex sum,where the vertex sum of a vertex v is the sum of labels of all edges entering v minus the sum of labels of all edges leaving v.If D has a local k-antimagic labeling,then we call D a local k-antimagic orientation of G.When k = 0,we regard k-antimagic labeling(orientation)as antimagic labeling(orientation).The famous Antimagic Labeling Conjecture and 1-2-3 Conjecture inspire us to consider this problem.The Antimagic Labeling Conjecture was proposed in 1990 and has received much attention,but has not been fully resolved yet.The difficulties lie in the requests of different labels on any two edges and different sums of incident edges of any two vertices.However,1-2-3 Conjecture only requires to distinguish adjacent vertices.Inspired by this,we began to study local antimagic labeling of graphs,and extend to directed graphs.Chang et al.conjectured that every connected graph admits a local antimagic orientation.In this paper,we proved that every d-degenerate graph admits a local(d + 2)-antimagic orientation,and the result holds for the list version,where each real number in the lists is positive.Since planar graphs are 5-degenerate,our result implies that every planar graph admits a local 7-antimagic orientation.