A Characterization for the Neighbor-Distinguishing Index of Planar Graphs

Abstract

Symmetry, such as structural symmetry, color symmetry and so on, plays an important role in graph coloring. In this paper, we use structural symmetry and color symmetry to study the characterization for the neighbor-distinguishing index of planar graphs. Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any two adjacent vertices admit different sets consisting of the colors of their incident edges. The neighbor-distinguishing index χa′(G) of G is the smallest number of colors in such an edge coloring of G. It was conjectured that if G is a connected graph with at least three vertices and G≠C5, then χa′(G)≤Δ+2. In this paper, we show that if G is a planar graph with maximum degree Δ≥13, then Δ≤χa′(G)≤Δ+1, and, further, χa′(G)=Δ+1 if and only if G contains two adjacent vertices of maximum degree.

Keywords

• planar graph
• neighbor-distinguishing edge coloring
• discharging method