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 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. Chang, He, Li, Pettie and Uitto 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 Õ((Δ)log 6 n ) rounds. These results improve the dependency on log n compared to the recent breakthrough result of Bernshteyn, 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 ((Δ, 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 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.

Authors

• Aleksander Bjørn Grodt Christiansen

Keywords

• distributed algorithms
• dynamic algorithms
• edge-colouring