Article ID Journal Published Year Pages File Type
4647183 Discrete Mathematics 2014 4 Pages PDF
Abstract

A proper [k][k]-edge coloring of a graph GG is a proper edge coloring of GG using colors from [k]={1,2,…,k}[k]={1,2,…,k}. A neighbor sum distinguishing [k][k]-edge coloring of GG is a proper [k][k]-edge coloring of GG such that for each edge uv∈E(G)uv∈E(G), the sum of colors taken on the edges incident to uu is different from the sum of colors taken on the edges incident to vv. By nsdi(G)(G), we denote the smallest value kk in such a coloring of GG. It was conjectured by Flandrin et al. that if GG is a connected graph without isolated edges and G≠C5G≠C5, then nsdi(G)≤Δ(G)+2(G)≤Δ(G)+2. In this paper, we show that if GG is a planar graph without isolated edges, then nsdi(G)≤max{Δ(G)+10,25}(G)≤max{Δ(G)+10,25}, which improves the previous bound (max{2Δ(G)+1,25}max{2Δ(G)+1,25}) due to Dong and Wang.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,