Adjacent vertex-distinguishing edge coloring of graphs

Marthe Bonamy 1 Nicolas Bousquet 1 Hervé Hocquard 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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].
Liste complète des métadonnées
Contributor : Alexandre Pinlou <>
Submitted on : Friday, January 29, 2016 - 11:50:06 AM
Last modification on : Thursday, May 31, 2018 - 2:54:03 PM

Links full text



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⟩



Record views