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

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^{\mathrm{\prime }}(G)$. If each edge $e$ is assigned a list $L^{\mathrm{\prime }}(e)$ and its colour must belong to $L^{\mathrm{\prime }}(e)$, the corresponding parameter is the strong list chromatic index ${\chi }_{s,\mathrm{\ell }}^{\mathrm{\prime }}(G)$. From the definitions, ${\chi }_s^{\mathrm{\prime }}(G)\le {\chi }_{s,\mathrm{\ell }}^{\mathrm{\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 $\mathrm{\Delta }$ is asymptotically at most $1.25{\mathrm{\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^{\mathrm{\prime }}(G)\le 1.625{\mathrm{\Delta }}^2$. Our second result improves this leading coefficient to $225\mathrm{/}142\approx 1.5845$. In fact, the proof establishes a stronger bound ${\chi }_{s,\mathrm{\ell }}^{\mathrm{\prime }}(G)\le \frac{225}{142}{\mathrm{\Delta }}^2+O(\mathrm{\Delta })$ for unit disk graphs.