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(G)$. If each edge $e$ is assigned a list $L'(e)$ and its colour must belong to $L'(e)$, the corresponding parameter is the strong list chromatic index $\chi'_{s,\ell}(G)$. From the definitions, $\chi'_s(G)\le\chi'_{s,\ell}(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\H{o}s and Ne\v{s}et\v{r}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\k{e}bski et al. proved that $\chi'_s(G) \leq 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}(G)\le\frac{225}{142} \Delta^2+O(\Delta)$ for unit disk graphs.