Strict Neighbor-distinguishing Coloring Of Graphs

A k-edge-coloring of a graph G is a mapping ?:E(G)? {1,2,…,k} such that?(e1)? ?(e2)for any two adjacent edges e1 and e2.The chromatic index ?'(G)of G is the smallest integer k such that G has a k-edge-coloring.For an edge coloring ? of G,we use C?(v)to denote the set of colors assigned to those edges incident to a vertex v? V(G).An edge-coloring ? of G is said to be strict neighbor-distinguishing if any two adjacent vertices u and v have C?(u)(?)C?(v)and C?(u)(?)C?(v).The strict neighbor-distinguishing chromatic index,denoted by ?'snd(G),of G is the smallest integer k such that G has a strict neighbor-distinguishing k-edge-coloring.A k-total-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)U E(G)receive different colors.The total chromatic number,denoted by ?"(G),of G is the smallest integer k such that G has a k-total-coloring.For a total-coloring ? of G,we use C?[v]to denote the set of colors assigned to a vertex v and those edges incident to v.A total-coloring ? of G is said to be strict neighbor-distinguishing if any two adjacent vertices u and v have C?[u](?)C?[v]and C?[u](?)C?[v].The strict neighbor-distinguishing total chromatic number,denoted by ?"snd(G),of G is the smallest integer k such that G has a strict neighbor-distinguishing k-total-coloring.A connected graph G is formal if ?(G)? 2.A graph G has a strict neighbor-distinguishing edge-coloring if and only if G is formal.By the definitions,it is easy to know that x'snd(G)??'(G)and ?"snd(G)??"(G).In 2008,Zhang introduced the strict neighbor-distinguishing index of graphs,and conjectured that:every connected graph G,different from C5,has ?'snd(G)?2?.Liu and Liu showed that there exists a constant c such that every graph G with ?? 1026 and having girth at least c? log ?satisfies ?'snd(G)??+301.In 2009,Zhang et al introduced the concept of the strict neighbor-distinguishing total-coloring of a graph,and conjectured that:every connected graph G has ?"snd(G)??+3.Zhu and Liu showed that every graph G with ?=3 has?"snd(G)? 6.In this Ph.D.dissertation,we study the strict neighbor-distinguishing edge-coloring of some graphs such as general graphs,graphs with smaller maximum degree,outerplanar graphs,K4-minor-free graphs.We also consider the strict neighbor-distinguishing total-coloring of general graphs and planar graphs with high girth.The dissertation consists of three chapters.In Chapter 1,we introduce some basic concepts and notations used in the disser-tation,give a chief survey for each topic and state the main results obtained in the dissertation.In Chapter 2,we investigate the strict neighbor-distinguishing edge-coloring of graph-s and show several results as follows:(1)every graph G has ?'snd(G)?3?-1;(2)every subcubic graph G has ?'snd(G)?7,and ?'snd(G)=7 if and only if G is a graph obtained from the graph K2,3 by inserting a 2-vertex into one edge;(3)every graph G with ?=4 has ?'snd(G)?9,and the upper bound 9 is tight;(4)every outerplanar graph G with?? 8 has ?'snd(G)??+5;(5)every K4-minor-free graph G has ?'snd(G)?2?+1,and?'snd(G)=2?+1 if and only if G is a graph obtained from the graph K2,? by inserting a 2-vertex into one edge.In Chapter 3,we study the strict neighbor-distinguishing total-coloring of graphs and obtain the following two results:(1)every graph G satisfies ?"snd(G)?2?;(2)every planar graph G of girth at least 11 and ?? 5 has ?"snd(G)??+2.