episciences.org_5404_1653752834
1653752834
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
09
2020
vol. 22 no. 1
Graph Theory
From light edges to strong edgecolouring of 1planar graphs
Julien
Bensmail
FranĂ§ois
Dross
HervĂ©
Hocquard
Eric
Sopena
A strong edgecolouring of an undirected graph $G$ is an edgecolouring where every two edges at distance at most~$2$ receive distinct colours. The strong chromatic index of $G$ is the least number of colours in a strong edgecolouring of $G$. A conjecture of Erd\H{o}s and Ne\v{s}et\v{r}il, stated back in the $80$'s, asserts that every graph with maximum degree $\Delta$ should have strong chromatic index at most roughly $1.25 \Delta^2$. Several works in the last decades have confirmed this conjecture for various graph classes. In particular, lots of attention have been dedicated to planar graphs, for which the strong chromatic index decreases to roughly $4\Delta$, and even to smaller values under additional structural requirements.In this work, we initiate the study of the strong chromatic index of $1$planar graphs, which are those graphs that can be drawn on the plane in such a way that every edge is crossed at most once. We provide constructions of $1$planar graphs with maximum degree~$\Delta$ and strong chromatic index roughly $6\Delta$. As an upper bound, we prove that the strong chromatic index of a $1$planar graph with maximum degree $\Delta$ is at most roughly $24\Delta$ (thus linear in $\Delta$). The proof of this result is based on the existence of light edges in $1$planar graphs with minimum degree at least~$3$.
01
09
2020
5404
https://hal.archivesouvertes.fr/hal02112188v3
https://hal.archivesouvertes.fr/hal02112188v2
https://hal.archivesouvertes.fr/hal02112188v1
10.23638/DMTCS2212
https://dmtcs.episciences.org/5404

https://dmtcs.episciences.org/5985/pdf