Recent papers have addressed different variants of the (Δ+ 1)-edge-colouring problem by
concatenating or gluing together many Vizing chains to form what Bernshteyn coined multi …

Linial's famous color reduction algorithm reduces a given $ m $-coloring of a graph with
maximum degree $\Delta $ to a $ O (\Delta^ 2\log m) $-coloring, in a single round in the …

Vizing's theorem states that every graph $ G $ of maximum degree $\Delta $ can be properly
edge-colored using $\Delta+ 1$ colors. The fastest currently known $(\Delta+ 1) $-edge …

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online (1+ o
(1)) Δ-edge-coloring algorithm exists for n-node graphs of maximum degree Δ= ω (log n) …

Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring
algorithm can edge color a graph optimally. Indeed, their work, titled" the greedy algorithm is …

In this article, we present a deterministic algorithm to compute an O (k Δ)-vertex coloring in O
(Δ/k)+ log* n rounds, where Δ is the maximum degree of the network graph and k≥ 1 can be …

We provide new deterministic algorithms for the edge coloring problem, which is one of the
classic and highly studied distributed local symmetry breaking problems. As our main result …

We study the edge-colouring problem, and give efficient algorithms where the number of
colours is parameterised by the graph's arboricity, $\alpha $. In a dynamic graph, subject to …

The complexity of distributed edge coloring depends heavily on the palette size as a function
of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the …

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 …