Faster Vizing and Near-Vizing Edge Coloring Algorithms
<|reference_start|>Faster Vizing and Near-Vizing Edge Coloring Algorithms: Vizing's celebrated theorem states that every simple graph with maximum degree $\Delta$ admits a $(\Delta+1)$ edge coloring which can be found in $O(m \cdot n)$ time on $n$-vertex $m$-edge graphs. This is just one color more than the trivial lower bound of $\Delta$ colors needed in any proper edge coloring. After a series of simplifications and variations, this running time was eventually improved by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to $O(m\sqrt{n\log{n}})$ time. This has effectively remained the state-of-the-art modulo an $O(\sqrt{\log{n}})$-factor improvement by Sinnamon in 2019.   As our main result, we present a novel randomized algorithm that computes a $\Delta+O(\log{n})$ coloring of any given simple graph in $O(m\log{\Delta})$ expected time; in other words, a near-linear time randomized algorithm for a ``near''-Vizing's coloring.   As a corollary of this algorithm, we also obtain the following results:   * A randomized algorithm for $(\Delta+1)$ edge coloring in $O(n^2\log{n})$ expected time. This is near-linear in the input size for dense graphs and presents the first polynomial time improvement over the longstanding bounds of Gabow et.al. for Vizing's theorem in almost four decades.   * A randomized algorithm for $(1+\varepsilon) \Delta$ edge coloring in $O(m\log{(1/\varepsilon)})$ expected time for any $\varepsilon = \omega(\log{n}/\Delta)$. The dependence on $\varepsilon$ exponentially improves upon a series of recent results that obtain algorithms with runtime of $\Omega(m/\varepsilon)$ for this problem.<|reference_end|>
@article{assadi2024faster,
    title={Faster Vizing and Near-Vizing Edge Coloring Algorithms},
    author={Sepehr Assadi},
    journal={arXiv preprint arXiv:2405.13371},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13371},
    primaryClass={cs.DS}
}