Strong edge colouring results improve graph colouring for disk graphs
Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
Discrete Mathematics
Summary
Strong edge colouring is a way to colour lines connecting dots so that certain patterns don’t overlap or interfere. The authors improved how well we can colour these connections for more complex shapes called disk graphs, which are like circles that can overlap. They also made the colouring rules for simpler shapes called unit disk graphs more efficient, reducing the number of colours needed. These advancements help better understand and manage how connections intersect in networks.
What this means in practice
- •For network schedulers: Use improved strong edge colouring bounds to optimize resource allocation in wireless networks modeled by disk graphs.
- •For wireless system designers: Apply reduced colour usage for channel assignment in unit disk graph models representing physical wireless nodes to reduce interference.
A theory result. No direct application yet.
Authors
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Sangita Saha, Saumya Sen
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,\ell}(G)$. From the definitions, $χ'_s(G)\leχ'_{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ő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) \leq 1.625 Δ^2$. Our second result improves this leading coefficient to $225/142 \approx 1.5845$. In fact, the proof establishes a stronger bound $χ'_{s,\ell}(G)\le\frac{225}{142} Δ^2+O(Δ)$ for unit disk graphs.