Vertex Distinguishing Colorings And Labelings Of Graphs

In this thesis,all graphs considered are finite and simple if no special statement.We use V(G),E(G),?(G)and ?(G)to denote the vertex set,edge set,maximum degree and minimum degree of graph G,respectively.Throughout this thesis,we work on graph coloring problems including locally irregular edge coloring,list 1-2-3 Conjecture,neighbor sum distinguishing edge coloring,Antimagic Labeling Conjecture and DP-coloring based on the well known Four-Color Conjecture and irregularity strength of graphs directly or indirectly.A graph is locally irregular if the degrees of all the adjacent vertices are distinct.A locally irregular edge-k-coloring of a graph G is an improper edge coloring with colors in {1,2,...,k} such that the graph induced on the edges of any color class is locally irregular.But not every graph admits a locally irregular edge coloring.We call a graph G decomposed if G admits a locally irregular edge coloring.In 2015,Baudon,Bensmail,Przybylo and Wozniak conjectured that any decomposed graphs are locally irregular edge-3-coloring.Recently,Bensmail et al.settled the first constant upper bound for the problem to 328 colors.Borut et al.improved this result to 220 later.In this thesis,we present an improvement of the bounds for decomposed general graphs,setting the best upper bounds to 184 by proving that every decomposed bipartite graph is locally irregular edge-5-coloring.We call a graph normal if there is no isolated edge in it.An edge-k-weighting ? of G is a function ?:E(G)? {1?2,...,k}.An edge-k-weighting is proper if ?e(?)u?(e)??e(?)v?(e)for every uv ? E(G).In 2004,Karonski,Luczak and Thomason made the well known 1-2-3 Conjecture:Every normal graph G has a proper edge-3-weighting.This conjecture received considerable attention.Up to now the latest result is k=5.We say a graph G is(k,k')-choosable if for any list assignment L which assigns to each vertex v a set L(v)of k real numbers,and assigns to each edge e a set L(e)of k' real numbers,there is a total weighting ?>:V(G)(?)E(G)? R such that ?(z)? L(z)for z ? V(G)UE(G),and any two adjacent vertices have distinct vertex sums,where vertex sum at v means that the sum of weights taking on the edges incident to v and the weight on v.In 2011,Wong and Zhu conjectured that every normal graph is(1,3)-choosable,which is clearly the list version of 1-2-3 Conjecture.Some special graphs was shown to be(1,3)-choosable,such as complete graphs,complete bipartite graphs,trees,Cartesian product of some special graphs,normal graph with maximum average degree less than 11/4 In 2015,Wang and Yan proved that any normal graph G is(1,[4?(G)+8/3])-choosable.We verify that every normal graph G is(1,?(G)+ 2)-choosable by applying some combinatorial methods.A proper edge coloring is an edge coloring with colors in {1,2,...,k} such that all the adjacent edges receive distinct colors.If we add the requirement of "proper edge coloring" on 1-2-3 Conjecture,then the coloring becomes neighbor sum distinguishing edge-k-coloring,or NSD-k-coloring for short.In 2013,Flandrin et al.studied the NSD-k-coloring of trees,cycles,complete graphs and complete bipartite graphs.Based on these results,they conjectured that if G is a graph with at least 3 vertices and G ? C5,then?'?(G)?(G)2.Flandrin et al.also proved that for each connected graph G with maximum degree ?(G)? 2,it holds that ?'?(G)?[7A(G)-4/2].Wang and Yan improved this bound to[10?(G)+2/3].Later,Przybylo proved that ch'?(G)? 2?(G)+ col(G)-1,where col(G)is the coloring number of G.Lately,Przybylo and Wong proved that ch'?(G)? ?(G)+ 3col(G)-4.We give a bound of general graphs,which is ch'?(G)??(G)+[5-col(G)+1/2]and covers the previous results.Dong et al.also studied NSD-k-colorings of sparse graphs.More precisely,they proved the following result:Let G be a normal graph.If mad(G)<5/2 and ?(G)? 5,then ?'?(G)?? + +1 where mad(G)=max(?).Later,Gao et al.improved the bound 5/2 to 8/3.We improve 8/3 to 3?-2/?(G).We also prove that if G is a normal graph with ?(G)>5 and mad(G)<3,then ??(G)??(G)(G)+ 2.Meanwhile,we verify that if ?(G)= 3 and mad(G)<5/2,then?'?(G)?5.A k-labeling of a graph G with m edges is an injection from E(G)to a set S of m + k positive real numbers,and the vertex sum at a vertex v ?V(G)is the sum of labels on the edges incident to v.A k-labeling of G without two vertices with a same vertex sum is called a vertex distinguishable labeling.A k-labeling is an antimagic labeling if it is vertex distinguishable and S= {1,2,...,m}.A graph is antimagic if it has an antimagic labeling.A k-labeling is local k-antimagic labeling if there is no two adjacent vertices with the same vertex sum.A graph is local k-antimagic if it has a local k-antimagric labeling.In 1990,Hartsfield and Ringel conjectured that every connected graph other than K2 is antimagic.In this thesis,we study two related problems of Antimagic Labeling Conjectures as follows.For any simple graph G,we define an orientation for all the edges of G such that G becomes a directed graph G.We call G an orientation of G.If G has an orientation G,and G admits a labeling such that all the vertices in G have distinct vertex sums,where the label set S ={1,2,...,m},then we call G an antimagic orientation of G,where the vertex sum of a vertex v in G means that the sum of labels on the incoming edges of v subtracts the sum of labels on the outgoing edges of v.In 2010,Hefetz,Mutze and Schwartz introduced this definition and they posted the following problems:Every connected graph admits an antimagic orientation.Meanwhile,they showed almost all regular graphs have an antimagic orientation.Observe that if a bipartite graph is antimagic,then it has an antimagic orientation obtained by directing all edges from one partite set to the other.Thus regular bipartite graphs have an antimagic orientation.A bipartite graph is biregular if vertices in each of the same partite set have the same degree.We prove that every biregular bipartite graph admits an antimagic orientation.Two sets of authors Arumugam et al.and Bensmail et al.independently con-jectured that every normal connected graph G is local antimagic with the label set S = {1,2,...,|E(G)|}.Bensmail et al.verified that a subcubic graph admits a local 6-antimagic labeling with S = {1,2,...,|E(G)|}+ 6},we improve this result by prov-ing that subcubic graphs are local antimagic.In their same paper,they also proved that every normal 2-degenerate graph admits a local 4-antimagic labeling with S ={1,2,...,}E(G)|+ 4},and every normal graph admits a local k-antimagic labeling with S= {1,2,...,|E(G)| + k},where k = min{2?(G),|E(G)|}.We contribute our two re-sults of general graphs.Let G be a normal graph with maximum degree ?(G).If all the vertices have odd degrees in G,then G is local(?(G)+ 1)-antimagic.Otherwise,G is local ?(G)-antimagic.We also prove that G is local[3col(G)+3/2]-antimagic.While solving a question on list coloring of planar graphs,Dvorak and Postle intro-duced the new notion of DP-coloring(they called it correspondence coloring).A DP-coloring of a graph G reduces the problem of finding.a coloring of G from a given list L to the problem of finding a "large" independent set in an auxiliary graph H(G,L),whose vertex set is {(v,c):v ? V(G)and c ? L(v)},and the edge set has two parts as follows:· for every vertex v?V(G),(v,c)is adjacent to(v,c'),where c,c' L(v);· for every edge uv ? E(G),(u,L(u))and(v,L(v))induce an arbitrary matching(may be empty).The idea is derived from the old reduction by Plesnevic and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G?DKk.For any list L with |L(v)|? k for each v ? V(G),if there exists an independent set of size |V(G)| in H,then we call G is DP-k-colorable.The minimal number k is called DP-chromatic number,denoted by ?DP(G).Obviously,it is always the case that ?DP(G)??l(G),but some differ quite a lot.In Chapter 4,we introduce DP-colorings for simple graphs and prove that planar graphs without 4-cycles adjacent to 3-cycles are DP-4-colorable.