2-distance Vertex-distinguishing Edge Coloring Of Graphs

A proper edge k-oloring of a graph G is a mapping Φ:E(G) →{1,2,..., k｝ such that Φ(e)≠ Φ(e’) for any two adjacent edges e and e’. Let CΦ(v) denote the set of colors assigned to the edges incident to a vertex v, i.e., CΦ(v)={Φ(uv)|uv ∈ E(G)}. The coloring Φ is called 2-distance vertex-distinguishing if CΦ(u)≠CΦ(v) for any pair of vertices u and v with d(u, v)= 2. The 2-distance vertex-distinguishing index χ’d2(G) of a graph G is the smallest integer k such that G has a 2-distance vertex-distinguishing edge coloring using k colors.The 2-distance vertex-distinguishing edge coloring of graphs is a special case of the r-strong edge coloring of graphs, introduced by Akbari et al. and independently by Zhang et al in 2006. Let r≥ 1 be an integer. The r-strong edge chromatic number χ’s(G,r) of a graph G is the minimum number of colors required for a proper edge coloring Φ of G such that any two vertices u and v with d(u, v)≤ r satisfy CΦ(u)≠ CΦ(v).If r= 1, then χ’s(G,1)=χ’a(G), which is called the adjacent vertex-distinguishing chromatic index. In 2002, Zhang et al introduced the adjacent vertex-distinguishing edge coloring of graphs and conjected:If G is a connected graph with|V(G)|≥ 6, then χ’a(G)≤ △+2. Balister et al. affirmed the conjecture for bipartite graphs and subcubic graphs. Using probabilistic method, Hatami showed that every graph G with △> 1020 has χ’a(G)≤△A+300. Akbari et al. proved that every graph G satisfies χ’a(G)≤3△. Wang et al. improved this bound to that χ’a(G)≤2.5△ for any graph G.In this master thesis, we study the 2-distance vertex-distinguishing edge coloring of graphs. The thesis consists of four chapters.In Chapter 1, we collect some basic notations, give a chief survey in this direction and state the main results obtained.In Chapter 2, we study the 2-distance vertex-distinguishing edge coloring of some special graphs. We determine the 2-distance vertex-distinguishing index χ’d2 of some classical graphs and unicycle graphs.In Chapter 3, we show that the 2-distance vertex-distinguishing index of a Halin graph is at most △+2.In Chapter 4, we investigate the 2-distance vertex-distinguishing edge coloring of outerplanar graphs G by showing that Χ’a2(G)≤ min{2△, △+8}. Moreover, for a class of special outerplanar graphs G, we show that Χ’d2 (C)≤ △+2.