Julien Bensmail ; François Dross ; Hervé Hocquard ; Eric Sopena - From light edges to strong edge-colouring of 1-planar graphs

dmtcs:5404 - Discrete Mathematics & Theoretical Computer Science, January 9, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-2
From light edges to strong edge-colouring of 1-planar graphsArticle

Authors: Julien Bensmail 1; François Dross 1; Hervé Hocquard ORCID2; Eric Sopena ORCID2

  • 1 Combinatorics, Optimization and Algorithms for Telecommunications
  • 2 Laboratoire Bordelais de Recherche en Informatique

A strong edge-colouring of an undirected graph $G$ is an edge-colouring 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 edge-colouring of $G$. A conjecture of Erdős and Neš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$.

Volume: vol. 22 no. 1
Section: Graph Theory
Published on: January 9, 2020
Accepted on: November 29, 2019
Submitted on: April 26, 2019
Keywords: Light edges,Strong edge-colouring,Strong chromatic index,1-planar graphs,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 1718 times.
This article's PDF has been downloaded 434 times.