Davies-Peck & Zhang's new algorithm kills LLL bottleneck for triangle-free graph coloring

Triangle-free coloring—assigning colors to vertices so no triangle is monochromatic—is a benchmark for sublogarithmic randomized distributed algorithms in the LOCAL model. The classic Pettie-Su algorithm uses Δ/k colors with O(k + log* n) applications of a distributed Lovász Local Lemma (LLL). But the LLL step itself was the bottleneck: known implementations required O(log_Δ n) or O(Δ/log Δ) + log^{O(1)} log n rounds. In this work, Davies-Peck and Zhang apply Davies' 'resilience' concept (SODA 2023) to rewrite the LLL instances so they solve in just log^{O(1)} log n rounds, effectively removing the LLL from the critical path.

The result is a clean O(k) + log^{O(1)} log n round complexity—for k above log^{ω(1)} log n, the LLL isn't even needed. As a corollary, they deliver the first log^{O(1)} log n-round algorithms for coloring triangle-free graphs with o(Δ) colors, breaking the previous sublogarithmic barrier. The framework also extends to girth-5 graphs, yielding a (1+ε)Δ/ln Δ coloring in the same round bound, which matches the best existential upper bound. To appear at DISC 2026, this paper marks a significant step toward making the LLL a non-issue in distributed coloring problems.