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 χ'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 χ's,ℓ(G). From the definitions, χ's(G)≤χ's,ℓ(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 Δ is asymptotically at most 1.25Δ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 χ's(G) ≤ 1.625 Δ2. Our second result improves this leading coefficient to 225/142 ≈ 1.5845. In fact, the proof establishes a stronger bound χ's,ℓ(G)≤225/142 Δ2+O(Δ) for unit disk graphs.
Related
- An improved bound for the intersection of two longest cycles in k-connected graphs
- An improved bound on the treewidth of planar graphs excluding a grid minor
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- An improved upper bound for oriented diameter of graphs with diameter $4$
- Isomorphisms of abelian Cayley graphs with their natural edge-colouring
BibTeX
@misc{das2026strong,
title = {{Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound}},
author = {Sandip Das and Sk Samim Islam and Aashirwad Mohapatra and Sangita Saha and Saumya Sen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34023},
eprint = {2609.34023},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34023},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
AU - Sandip Das
AU - Sk Samim Islam
AU - Aashirwad Mohapatra
AU - Sangita Saha
AU - Saumya Sen
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.34023
UR - https://arxiv.org/abs/2609.34023
AB - 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 χ'_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 χ'_s,ℓ(G). From the definitions, χ'_s(G)≤χ'_s,ℓ(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 Δ is asymptotically at most 1.25Δ^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 χ'_s(G) ≤ 1.625 Δ^2. Our second result improves this leading coefficient to 225/142 ≈ 1.5845. In fact, the proof establishes a stronger bound χ'_s,ℓ(G)≤225/142 Δ^2+O(Δ) for unit disk graphs.
ER -