Strong chromatic index of planar graphs with large girth

Gerard Jennhwa Chang (1) , Mickaël Montassier (2) , Arnaud Pêcher (3, 4) , André Raspaud (4)

1 TIMS - Taida Institute of Mathematical Science
2 ALGCO - Algorithmes, Graphes et Combinatoire
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
4 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.

Mots clés: Planar graphs; Edge coloring; 2-distance coloring; Strong edgecoloring

Domaines: Sciences de l'information et de la communication

Gerard Jennhwa Chang, Mickaël Montassier, Arnaud Pêcher, André Raspaud. Strong chromatic index of planar graphs with large girth. Discussiones Mathematicae Graph Theory, 2014, 34 (4), pp.723-733. ⟨10.7151/dmgt.1763⟩. ⟨hal-00920932⟩