Edge-partitions of graphs and their neighbor-distinguishing index

Abstract A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by χ a ′ ( G ) . A graph is normal if it contains no isolated edges. Let G be a normal graph, and let Δ ( G ) and χ ′ ( G ) denote the maximum degree and the chromatic index of G , respectively. We modify the previously known techniques of edge-partitioning to prove that χ a ′ ( G ) ≤ 2 χ ′ ( G ) , which implies that χ a ′ ( G ) ≤ 2 Δ ( G ) + 2 . This improves the result in Wang et al. (2015), which states that χ a ′ ( G ) ≤ 5 2 Δ ( G ) for any normal graph. We also prove that χ a ′ ( G ) ≤ 2 Δ ( G ) when Δ ( G ) = 2 k , k is an integer with k ≥ 2 .