Article ID Journal Published Year Pages File Type
8903130 Discrete Mathematics 2018 15 Pages PDF
Abstract
A proper k-edge-coloring of a graph with colors in {1,2,…,k} is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least 6 vertices has an NSD edge coloring with at most Δ+2 colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD 6-edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vušković, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD 6-edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD 6-edge-coloring.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,