On Neighbor Distinguishing Coloring And Neighbor Sum Distinguishing Coloring Of Graphs

Graph coloring problem originated from the famous "Four Color Problem".The"Four Color Problem" is one of the most famous and the most difficult problems in graph theory and even the field of mathematics.Graph coloring is an important branch in graph theory,which has a very wide application in many fields such as computer science and channel assignment and so on.Let G be a simple graph,where V(G)and E(G)denote the set of vertices and edges of G,and ?(G)denote the maximum vertex degree of G.A graph G is called a planar graph if G can be embedded in the Euclidean plane such that any two edges intersect only at their ends.A plane graph is a particular drawing of a planar graph in the Euclidean plane.A proper edge k-coloring of a graph G is a mapping ?:E(G)?{1,2,...k} such that any two adjacent edges receive different colors.Given a proper edge k-coloring? of G,we use C_?(v)= {?{xv)|xv ? E(G)} to denote the set of colors assigned to those edges incident to a vertex v and S_?(v)to denote the sum of colors in C_?(v).The coloring ? is called an neighbor distinguishing edge k-coloring(an NDE-h-coloring for short)if C_?(u)? C_?(v)for each edge uv ? E(G).The neighbor distinguishing index?'a(G)of G is the smallest integer k such that G has an NDE-k-coloring.The coloring? is called an neighbor sum distinguishing edge k-coloring(an NSDE-k-coloring for short)if S_?(u)? S_?(v)for each edge uv ? E(G).The neighbor sum distinguishing index ?'?(G)of G is the smallest integer k such that G has an NSDE-k-coloring.If S_?(u)? S_?(v),then C_?(u)? C_?(v).Thus,an NSDE-coloring is an extension of an NDE-coloring.A proper total k-coloring of a graph G is a mapping ?:V(G)? E(G)?{1,2,...,k} such that any two adjacent or incident elements in V{G)? E(G)re-ceive different colors.Given a proper total k-coloring ? of we use C_?(v)={?(v)}?(?(xv)|xv ? E(G)} to denote the set of colors assigned to a vertex v and those edges incident to v.The coloring)is called an neighbor distinguishing total k-coloring(an NDT-k-coloring for short)if C_?(u)? C_?(v)for each edge uv ? E(G).The neighbor distinguishing total chromatic number ?_a~"(G)of G is the smallest integer k such that G has an NDT-k-coloring.This PhD dissertation focuses on three coloring problems of graphs,including NDE-coloring,NDT-coloring and NSDE-coloring.We use the Discharging method and Combinatorial Nullstellensatz to show some main results.It consists of four chapters as follows.In Chapter 1,we introduce some basic concepts' and notations used in the dis-sertation,give a chief survey in each topic and state the main results obtained in the dissertation.In Chapter 2,we study the NDE-colorings of general graphs.It is proved that X'a(G)? 2?(G)if 4 ? ?(G)? 6 and ?'a(G)? 2.5?(G)if ?(G)>7.This improves a known result that ?'a(G)? 2.5?(G)+ 5,due to Zhang,Wang and Lih.Moreover,we prove that ?'a(G)?5/3?(G)+ 13/3 if each edge of G is incident to at least one ?(G)-vertex.In Chapter 3,we study the NDT-colorings of planar graphs.In 2005,Zhang et al.posed the conjecture:If G is a graph with at least two vertices,then ?_a~"(G)??(G)+ 3.For a planar graph G,we prove the following three results:(1)If ?(G)= 9,then ?_a~"(G)?12;(2)If?(G)= 12,then ?_a~"(G)? 14;(3)If ?(G)= 13,then ?_a~"(G)= 15 if and only if G contains two adjacent vertices of maximum degree.These consequences extend the following three known results about planar graphs:(i)If ?(G)?10,then ?_a~"(G)? ?(G)+ 3;(ii)If A(G)? 13,then ?_a~"(G)? ?(G)+ 2;(iii)If ?(G)? 14,then ?_a~"(G)=?(G)+ 2 if and only if G contains two adjacent vertices of maximum degree.In Chapter 4,we study the NSDE-colorings of subcubic graphs.In 2013,Flandrin et al.proposed the conjecture:If G is a graph on at least 3 vertices and G ? G5,then?'?(G)? ?(G)+ 2.They also proved that ?'?(G)? 8 for every subcubic graph G.By a meticulous structural analysis,we improve this result to that ?'?(G)? 6.Moreover,we give some results on the neighbor sum distinguishing list index of subcubic graphs.