Neighbor Sum Distinguishing Edge Coloring Of Some Graphs

A proper k-edge coloring 0 of a graph G is a mapping φ:E(G)→｛1,2,…,k}such that each adjacent edges receive different colors.Let f(v)be the sum of colors on the edges incident with v.φ is called a k-neighbor sum distinguishing edge coloring if f(u)≠ f(v)for each edge uv ∈ E(G).The smallest k such that G has a k-neighbor sum distinguishing edge coloring is called the neighbor sum distinguishing index,denoted by χ∑’(G).Let △(G)and mad(G)be the maximum degree and the maximum average degree of a graph G,respectively.In 2011,Flandrin et al.proposed a conjecture for the neighbor sum distinguishing edge coloring,if G is a connected graph on at least 3 vertices and G≠C5,thenχ∑’(G)≤△(G)+ 2.In this paper,by using Combinatorial Nullstellensatz and discharging method,we study the neighbor sum distinguishing edge colorings of K4-minor free graphs,a kind of sparse graphs and planar graphs with girth at least 5.We get the following results:(1)Let G be a K4-minor free graph without isolated edges and △(G)≥6.If G has no adjacent vertices of maximum degree,then χ∑’(G)= △(G),otherwise,χ∑’(G)= △(G)+1.(2)Let G be a graph without isolated edges,△(G)≥ 6 and mad(G)≤5/2.If G has no adjacent vertices of maximum degree,then χ∑’(G)= △(G),otherwise,χ∑’(G)= △(G)+ 1.(3)If G is a planar graph with girth at least 5 and without isolated edges,thenχ∑’(G)≤ max{△(G)+ 2,9}.For graphs with maximum degree at least 6 and without isolated edges,if they are K4-minor free graphs or graphs with mad(G)≤5/2，Conclusion(1)and Conclusion(2)determine the neighbor sum distinguishing indices;Conclusion(3)implies that the conjecture of neighbor sum distinguishing edge coloring is true for a planar graph G with girth at least 5 and △(G)≥ 7.