The Power of Multi-step Vizing Chains

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-step Vizing chains. In this paper, we consider the most general definition of this term and apply different multi-step Vizing chain constructions to prove combinatorial properties of edge-colourings that lead to (improved) algorithms for computing edge-colouring across different models of computation. This approach seems especially powerful for constructing augmenting subgraphs which respect some notion of locality. First, we construct strictly local multi-step Vizing chains and use them to show a local version of Vizing’s Theorem thus confirming a recent conjecture of Bonamy, Delcourt, Lang and Postle. That is, we show that there exists a proper edge-colouring of a graph such that every edge uv receives a colour from the list {1,2, …, max{d(u),d(v)}+1}. Our proof is constructive and also implies an O(n² Δ) time algorithm for computing such a colouring. Then, we show that for any uncoloured edge there exists an augmenting subgraph of size O(Δ⁷logn), answering an open problem of Bernshteyn. Chang, He, Li, Pettie and Uitto show a lower bound of Ω(Δ log 𝑛 /Δ) for the size of augmenting subgraphs, so the upper bound is asymptotically tight up to Δ factors. These ideas also extend to give a faster deterministic LOCAL algorithm for (Δ + 1)-edge-colouring running in Õ(poly(Δ)log⁶ n) rounds. These results improve the dependency on logn compared to the recent breakthrough result of Bernshteyn, who showed the existence of augmenting subgraphs of size O(Δ⁶log² n), and used these to give the first (Δ + 1)-edge-colouring algorithm in the LOCAL model running in O(poly(Δ, logn)) rounds. Finally for dynamic graphs, we show how to maintain a(1+ε)Δ-edge-colouring fully adaptive to Δ in O(ε⁻⁶ log⁹ n log⁶ Δ) worst-case update time w.h.p without any restrictions on Δ. This should be compared to the edge-colouring algorithm of Duan, He and Zhang that runs in O(ε⁻⁴log⁸ n) amortised update time w.h.p under the condition that Δ = Ω(ε⁻²log² n). Our algorithm avoids the use of O(ε⁻¹logn) copies of the graph, resulting in a smaller space consumption and an algorithm with provably low recourse.