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.