Adjacent vertex-distinguishing edge coloring of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Adjacent vertex-distinguishing edge coloring of graphs


An adjacent vertex-distinguishing edge coloring (AVD-coloring) of a graph is a proper edge coloring such that no two neighbors are adjacent to the same set of colors. Zhang et al. [17] conjectured that every connected graph on at least 6 vertices is AVD (Δ + 2)-colorable, where A is the maximum degree. In this paper, we prove that (Δ + 1) colors are enough when A is sufficiently larger than the maximum average degree, denoted mad. We also provide more precise lower bounds for two graph classes: planar graphs, and graphs with mad < 3. In the first case, Δ ≥ 12 suffices, which generalizes the result of Edwards et al. [7] on planar bipartite graphs. No other results are known in the case of planar graphs. In the second case, Δ ≥ 4 is enough, which is optimal and completes the results of Wang and Wang [14] and of Hocquard and Montassier [9].

Dates and versions

lirmm-01264408 , version 1 (29-01-2016)



Marthe Bonamy, Nicolas Bousquet, Hervé Hocquard. Adjacent vertex-distinguishing edge coloring of graphs. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2013, Pise, Italy. pp.313-318, ⟨10.1007/978-88-7642-475-5_50⟩. ⟨lirmm-01264408⟩
156 View
0 Download



Gmail Mastodon Facebook X LinkedIn More