Edge-Coloring Algorithms for Bounded Degree Multigraphs

MaRDI QIDQ6443580zbMATH OpenFDO

Authors Abhishek Dhawan

Publication date 13 July 2023

Abstract: In this paper, we consider algorithms for edge-coloring multigraphs $G$ of bounded maximum degree, i.e., $Delta(G)=O(1)$. Shannon's theorem states that any multigraph of maximum degree $Delta$ can be properly edge-colored with $lfloor3Delta/2floor$ colors. Our main results include algorithms for computing such colorings. We design deterministic and randomized sequential algorithms with running time $O(nlogn)$ and $O(n)$, respectively. This is the first improvement since the $O(n^2)$ algorithm in Shannon's original paper, and our randomized algorithm is optimal up to constant factors. We also develop distributed algorithms in the $mathsfLOCAL$ model of computation. Namely, we design deterministic and randomized $mathsfLOCAL$ algorithms with running time $ildeO(lo{g}^{5}n)$ and $O(lo{g}^{2}n)$, respectively. The deterministic sequential algorithm is a simplified extension of earlier work of Gabow et al. in edge-coloring simple graphs. The other algorithms apply the entropy compression method in a similar way to recent work by the author and Bernshteyn, where the authors design algorithms for Vizing's theorem for simple graphs. We also extend their results to Vizing's theorem for multigraphs.

This page was built for publication: Edge-Coloring Algorithms for Bounded Degree Multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443580)