Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$

Hervé Hocquard 1 Mickaël Montassier 2, 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : An adjacent vertex-distinguishing edge coloring, or avd-coloring, of a graph G is a proper edge coloring of G such that no pair of adjacent vertices meets the same set of colors. Let mad(G) and Δ(G) denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper, we prove that every graph G with Δ(G)≥5 and mad(G)<3−2/Δ can be avd-colored with Δ(G)+1 colors. This completes a result of Wang and Wang (J. Comb. Optim. 19:471-485, 2010).
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2012, pp.9. 〈10.1007/s10878-011-9444-9〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782842
Contributeur : Mickael Montassier <>
Soumis le : mercredi 30 janvier 2013 - 16:43:33
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Hervé Hocquard, Mickaël Montassier. Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$. Journal of Combinatorial Optimization, Springer Verlag, 2012, pp.9. 〈10.1007/s10878-011-9444-9〉. 〈lirmm-00782842〉

Partager

Métriques

Consultations de la notice

184