Edge-coloring sparse graphs with Δ colors in quasilinear time

2024/01/24 by Kowalik, Lukasz · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2401.13839

Abstract

In this paper we show that every graph G of bounded maximum average degree \rm mad(G) and with maximum degree Δ can be edge-colored using the optimal number of Δ colors in quasilinear time, whenever Δ≥ 2\rm mad(G). The maximum average degree is within a multiplicative constant of other popular graph sparsity parameters like arboricity, degeneracy or maximum density. Our algorithm extends previous results of Chrobak and Nishizeki [J. Algorithms, 1990] and Bhattacharya, Costa, Panski and Solomon [ESA 2024].

Cited by

• Vizing's Theorem in Deterministic Almost-Linear Time
• The planar edge-coloring theorem of Vizing in O(nlog n) time

Related

• A linear-time algorithm for (1+ε)Δ-edge-coloring
• Simple and Near-Optimal Distributed Coloring for Sparse Graphs
• A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
• Fast and Simple Edge-Coloring Algorithms
• Vizing's Theorem in Deterministic Almost-Linear Time