Strict Neighbor-distinguishing Edge Coloring And Interval Edge Coloring Of Graphs

An edge-h-coloring of a graph G is a mapping φ:E(G)→{1,2,...,k} such that any two adjacent edges receive different colors.The chromatic index of G denoted χ’(G),is the smallest k such that G has an edge-k-coloring.Given an edge-k-coloring φ of G,we use Cφ(v)to denote the set of colors assigned to the edges incident with a vertex v.We say that φ is strict neighbor-distinguishing if |Cφ(u)\Cφ(v)|≥ 1 and |Cφ(v)\Cφ(u)|≥ 1 for any pair of adjacent vertices u and v.The strict neighbor distinguishing index χ’snd(G)of G is the smallest k such that G has a strict neighbor-distinguishing edge-k-coloring.Obviously,G has a strict neighbor-distinguishing edge coloring if and only if G contains no isolated edges,and χ’snd(G)≥χ’(G).The strict neighbor-distinguishing edge coloring of graphs was introduced by Zhang(2008).Let Hn(n≥ 2)denote the graph obtained from a bipartite graph K2,n by inserting a 2-vertex into one edge.Thus χ’snd(Hn)=2n+1=2△(Hn)+1.Based on this fact,Gu et al.raised the following conjecture.For G≠ H△,has χ’snd(G)≤2△.In this research,we proposed the conception of local neighbor-distinguishing coloring,if |C(u)\C(v)|≥1 and\C(v)\C(u)|≥1 for any pair of adjacent 2+-vertices u and v.The local neighbor-distinguishing chromatic index χ’lnd(G)of G is the smallest k such that G has a LNDE-k-coloring.A proper edge coloring of a graph G is called interval edge coloring if Cφ(v)is consecutive(i.e.,those colors form an interval of integers).The interval edge coloring chromatic index χ’iec(G)of G is the smallest k such that G has a IEC-k-coloring.This topic was introduced by Asratian and Kamalian in 1987.Not every graph has such a coloring,for example K3.One can see that any graph admitting an interval edge coloring must be of class 1,and every graph of class 2 does not have such a coloring.In this Ph.D.dissertation,we study the strict neighbor-distinguishing edge coloring of general planar graphs,3-connected planar graphs,and special planar graphs.And the interval edge coloring of complete tripartite graph Kl,m,n and(α,β)-biregular bigraph.The dissertation consists of five chapters as follows.In Chapter 1,we collect some concepts and notation used in the dissertation,give a detailed survey on the research progress of related areas,and state the main results obtained in the dissertation.In Chapter 2,we study the strict neighbor-distinguishing edge coloring of general planar graphs and 3-connected graphs.Main results are follows:(1)If G is a formal planar graph,then χ’snd(G)≤「2.8△(?)+4.(2)If G is a 3-connected planar graph,then χ’snd(G)≤ △+23.(3)If G is a planar Hamiltonian graph,then χ’snd(G)≤△+6.In Chapter 3,we investigate the strict neighbor-distinguishing edge coloring of special planar graphs,and confirm the following conclusions:(1)If G is a planar graph with g(G)≥5,then χ’snd(G)≤△+25.(2)If G is a planar graph without 4-cycles,then χ’snd(G)≤△+300.In Chapter 4,we focus on the interval edge coloring of complete tripartite graph Kl,m,n and(α,β)-biregular bigraph,and confirm the following conclusions:(1)some conditions of Kl,m,n has interval edge coloring of l=2,3,4.(2)some conditions of(α,β)-biregular bigraph has interval edge coloring.In Chapter 5,we focus on the future work about the two topics.