Strong edge coloring sparse graphs

Abstract : A strong edge coloring of a graph is a proper edge coloring such that no edge has two incident edges of the same color. Erdős and Nešetřil conjectured in 1989 that $5 /4∆2$ colors are always enough for a strong edge coloring, where $∆$ is the maximum degree of the graph. In the specific case where $∆ = 4$, we prove this to be true when there is no subgraph with average degree at least $4 − 1/5$ , and show that fewer colors are necessary when the graph is even sparser.
Type de document :
Article dans une revue
Electronic Notes in Discrete Mathematics, Elsevier, 2015, The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, 49, pp.773-778. 〈10.1016/j.endm.2015.06.104〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264420
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 27 juillet 2016 - 10:25:02
Dernière modification le : jeudi 25 janvier 2018 - 21:54:03

Fichier

degree4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Julien Bensmail, Marthe Bonamy, Hervé Hocquard. Strong edge coloring sparse graphs. Electronic Notes in Discrete Mathematics, Elsevier, 2015, The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, 49, pp.773-778. 〈10.1016/j.endm.2015.06.104〉. 〈lirmm-01264420〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

88