A fast distributed algorithm for (Δ + 1)-edge-coloring

Autor:	Anton Bernshteyn
Rok vydání:	2022
Předmět:	Combinatorics Edge coloring Computational Theory and Mathematics Matching (graph theory) Computer Science::Discrete Mathematics Distributed algorithm Discrete Mathematics and Combinatorics Graph (abstract data type) MathematicsofComputing_DISCRETEMATHEMATICS Theoretical Computer Science Mathematics
Zdroj:	Journal of Combinatorial Theory, Series B. 152:319-352
ISSN:	0095-8956
DOI:	10.1016/j.jctb.2021.10.004
Popis:	We present a deterministic distributed algorithm in the LOCAL model that finds a proper ( Δ + 1 ) -edge-coloring of an n-vertex graph of maximum degree Δ in poly ( Δ , log ⁡ n ) rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only Δ + 1 colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Grebik and Pikhurko.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::59540d8c37e6c5773aef39b34e26c8e6 https://doi.org/10.1016/j.jctb.2021.10.004 Zobrazit plný text záznamu Full Text from ScienceDirect