Triangle-Free Coloring in LOCAL via Resilient Lov\'asz Local Lemma

Abstract

The Lov\'asz Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\frac{\Delta}{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln \Delta$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_\Delta n)$ or $O(\frac{\Delta}{\log\Delta})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the'resilience'definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{\omega(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(\Delta)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)\Delta/\ln \Delta$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.