Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647086 | Discrete Mathematics | 2015 | 10 Pages |
Abstract
Given a proper edge kk-coloring ϕϕ and a vertex v∈V(G)v∈V(G), let Cϕ(v)Cϕ(v) denote the set of colors used on edges incident to vv with respect to ϕϕ. The adjacent vertex distinguishing index of GG, denoted by χa′(G), is the least value of kk such that GG has a proper edge kk-coloring which satisfies Cϕ(u)≠Cϕ(v)Cϕ(u)≠Cϕ(v) for any pair of adjacent vertices uu and vv. In this paper, we show that if GG is a connected planar graph with maximum degree Δ≥12Δ≥12 and without 3-cycles, then Δ≤χa′(G)≤Δ+1, and χa′(G)=Δ+1 if and only if GG contains two adjacent vertices of maximum degree. This extends a result in Edwards et al. (2006), which says that if GG is a connected bipartite planar graph with Δ≥12Δ≥12 then χa′(G)≤Δ+1.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Danjun Huang, Zhengke Miao, Weifan Wang,