Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$ - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Optimization Année : 2013

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

Résumé

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).

Dates et versions

lirmm-00782842 , version 1 (30-01-2013)

Identifiants

Citer

Hervé Hocquard, Mickaël Montassier. Adjacent vertex-distinguishing edge coloring of graphs with maximum degree $\Delta$. Journal of Combinatorial Optimization, 2013, 26 (1), pp.152-160. ⟨10.1007/s10878-011-9444-9⟩. ⟨lirmm-00782842⟩
141 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More