2026-07-26T04:38:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21094 2024-09-23T09:13:16Z ddc:004 open_access

Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay Graph Algorithms Edge Coloring Arboricity Vizing’s theorem asserts the existence of a (Δ+1)-edge coloring for any graph G, where Δ = Δ(G) denotes the maximum degree of G. Several polynomial time (Δ+1)-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is Õ(min{m √n, m Δ}), by Gabow, Nishizeki, Kariv, Leven and Terada from 1985, where n and m denote the number of vertices and edges in the graph, respectively. Recently, Sinnamon shaved off a polylog(n) factor from the time bound of Gabow et al. The arboricity α = α(G) of a graph G is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph’s "uniform density". While α ≤ Δ in any graph, many natural and real-world graphs exhibit a significant separation between α and Δ. In this work we design a (Δ+1)-edge coloring algorithm with a running time of Õ(min{m √n, m Δ})⋅ α/Δ, thus improving the longstanding time barrier by a factor of α/Δ. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., α = Õ(1)) as well as when α = Õ(Δ/√n). Our algorithm builds on Gabow et al.’s and Sinnamon’s algorithms, and can be viewed as a density-sensitive refinement of them. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bhattacharya and Martín Costa and Nadav Panski and Shay Solomon 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.23 urn:nbn:de:0030-drops-210945 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode