The Power of Multi-step Vizing Chains
Aleksander B. G. Christiansen · 2023
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.