The Power of Multi-step Vizing Chains

Recent papers [Ber22, DHZ19, GP20] have addressed different variants of the (∆ + 1)-edgecolouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn [Ber22] 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 edgecolouring 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 [BDLP20]. 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, . . . , maxd(u), d(v) + 1. Our proof is constructive and also implies an O(n 2 ∆) time algorithm for computing such a colouring. Then, we show that for any uncoloured edge there exists an augmenting subgraph of size O(∆ 7 log n), answering an open problem of Bernshteyn [Ber22]. Chang, He, Li, Pettie and Uitto [CHL + 18] show a lower bound of Ω(∆ log n ∆ ) 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 6 n) rounds. These results improve the dependency on log n compared to the recent breakthrough result of Bernshteyn [Ber22], who showed the existence of augmenting subgraphs of size O(∆ 6 log 2 n), and used these to give the first (∆ + 1)-edge-colouring algorithm in the LOCAL model running in O(poly(∆, log n)) rounds. Finally for dynamic graphs, we show how to maintain a(1+ε)∆-edge-colouring fully adaptive to ∆ in O(ε -6 log 9 n log 6 ∆) 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 [DHZ19] that runs in O(ε -4 log 8 n) amortised update time w.h.p under the condition that ∆ = Ω(ε -2 log 2 n). Our algorithm avoids the use of O(ε -1 log n) copies of the graph, resulting in a smaller space consumption and an algorithm with provably low recourse.