Authors: Vučković, Bojan 
Title: Edge-partitions of graphs and their neighbor-distinguishing index
Journal: Discrete Mathematics
Volume: 340
Issue: 12
First page: 3092
Last page: 3096
Issue Date: 1-Dec-2017
Rank: M22
ISSN: 0012-365X
DOI: 10.1016/j.disc.2017.07.005
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)≤[Formula presented]Δ(G) for any normal graph. We also prove that χa′(G)≤2Δ(G) when Δ(G)=2k, k is an integer with k≥2.
Keywords: Edge-partition | Maximum degree | Neighbor-distinguishing edge coloring
Publisher: Elsevier

Show full item record


checked on Jul 13, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.