Strong edge coloring sparse graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Electronic Notes in Discrete Mathematics Year : 2015

Strong edge coloring sparse graphs


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.
Fichier principal
Vignette du fichier
degree4.pdf (248.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01264420 , version 1 (27-07-2016)



Julien Bensmail, Marthe Bonamy, Hervé Hocquard. Strong edge coloring sparse graphs. Electronic Notes in Discrete Mathematics, 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⟩
231 View
334 Download



Gmail Facebook X LinkedIn More