Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound

Abstract

A strong edge colouring of a graph $G$ is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index ${\chi }_s^{\prime }(G)$. If each edge $e$ is assigned a list $L^{\prime }(e)$ and its colour must belong to $L^{\prime }(e)$, the corresponding parameter is the strong list chromatic index ${\chi }_{s,\ell }^{\prime }(G)$. From the definitions, ${\chi }_s^{\prime }(G)\le {\chi }_{s,\ell }^{\prime }(G)$. Barrett et al. gave an $8$-approximation for strong edge colouring on unit disk graphs and Grelier et al. improved the approximation factor to $6$. Our first result extends this factor-$6$ guarantee from unit disk graphs to the strictly larger class of disk graphs. In another direction, Erdős and Nešetřil conjectured that the strong chromatic index of a graph of maximum degree $\Delta$ is asymptotically at most $1.25{\Delta }^2$. The best published general asymptotic upper bound has leading coefficient $1.772$, due to Hurley et al. For unit disk graphs, Dębski et al. proved that ${\chi }_s^{\prime }(G)\le 1.625{\Delta }^2$. Our second result improves this leading coefficient to $225/142\approx 1.5845$. In fact, the proof establishes a stronger bound ${\chi }_{s,\ell }^{\prime }(G)\le \frac{225}{142}{\Delta }^2+O(\Delta )$ for unit disk graphs.

arXiv comment14 pages, 2 figures