论文标题
多步数链的力量
The Power of Multi-Step Vizing Chains
论文作者
论文摘要
最近的论文[BER'2022]，[GP'2020]，[DHz'2019]通过将或粘合在一起形成Bernshteyn [ber'2022] ccuined \ emph {multi-step {Multi-step vized Chinains}来解决（δ+ 1） - 边缘着色问题的不同变体。 在本文中，我们提出了对该术语的更一般的定义。然后，我们应用多步链链构造来证明边缘着色的组合性能，这些构图导致（改进）算法用于计算不同计算模型的边缘着色。这种方法似乎对于构建尊重某些地方概念的增强子图特别有力。 首先，我们构建了严格的本地多步数，并使用它们来展示Vizings定理的本地版本，从而确认了最近的Bonamy，Delcourt，Lang和Postle [BDLP'2020]的猜想。我们的证明是建设性的，也意味着用于计算这种着色的算法。 然后，我们表明，对于任何未颜色的边缘，存在大小O（δ^{7} \ log n）的增强子图，回答了Bernshteyn [ber'2022]的开放问题。 Chang，He，Li，Pettie和Uitto [Chlpu'2018]显示了此类增强子图的大小的ω（δ\ log \ frac {n}δ）的下限，因此上限紧密至δ和恒定因子。 这些想法还扩展到了（δ+ 1） - 边缘着色的速度更快的确定性局部算法，以\ tilde {o}（\ poly（δ）\ log^6 n）弹性。这些结果改善了Bernshteyn [Ber'2022]的最新突破结果，后者表明存在大小O（δ^6 \ log^2 n）的增强子图，并使用它们给出了第一个（δ+ 1） - 边缘颜色算法在o（\ poly（δ，\ fold log n））的局部模型中。 ...（有关摘要的其余部分，请参见论文）
Recent papers [Ber'2022], [GP'2020], [DHZ'2019] have addressed different variants of the (Δ+ 1)-edge colouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn [Ber'2022] coined \emph{multi-step Vizing chains}. In this paper, we propose a slightly more general definition of this term. We then apply 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 Vizings Theorem thus confirming a recent conjecture of Bonamy, Delcourt, Lang and Postle [BDLP'2020]. Our proof is constructive and also implies an 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 [Ber'2022]. Chang, He, Li, Pettie and Uitto [CHLPU'2018] show a lower bound of Ω(Δ\log \frac{n}Δ) for the size of such augmenting subgraphs, so the upper bound is tight up to Δand constant factors. These ideas also extend to give a faster deterministic LOCAL algorithm for (Δ+ 1)-edge colouring running in \tilde{O}(\poly(Δ)\log^6 n) rounds. These results improve the recent breakthrough result of Bernshteyn [Ber'2022], 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. ... (see paper for the remaining part of the abstract)
