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].
Type de document :
Communication dans un congrès
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2013, Pise, Italy. pp.313-318, 2013, The Seventh European Conference on Combinatorics, Graph Theory and Applications. 〈10.1007/978-88-7642-475-5_50〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264408
Contributeur : Alexandre Pinlou <>
Soumis le : vendredi 29 janvier 2016 - 11:50:06
Dernière modification le : jeudi 31 mai 2018 - 14:54:03

Lien texte intégral

Identifiants

Citation

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, 2013, The Seventh European Conference on Combinatorics, Graph Theory and Applications. 〈10.1007/978-88-7642-475-5_50〉. 〈lirmm-01264408〉

Partager

Métriques

Consultations de la notice

139