2024/07/05 by Anton Bernshteyn, Bernshteyn, Anton, Abhishek Dhawan +1 · 1 citation
Physics and Astronomy · Decision Sciences · Computer Science · #Color Science and Applications #Scheduling and Timetabling Solutions #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2407.04887
We present a randomized algorithm that, given a constant ε> 0, outputs a proper (1+ε)Δ-edge-coloring of an m-edge simple graph G of maximum degree Δ≥ 1/ε in O(m) time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of Δ. Indeed, even for edge-coloring with 2Δ- 1 colors (i.e., meeting the "greedy" bound), no such linear-time algorithm has been previously known.