CS Paper Radar

Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma

Peter Davies-Peck, Xusheng Zhang

cs.DC cs.DS ·submitted 2026-08-13 15:21 UTC · v1
publishedbenchmarktheory

Abstract

The Lovász 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Δ{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln Δ$) 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_Δn)$ or $O(\fracΔ{\logΔ})+\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^{ω(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(Δ)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)Δ/\ln Δ$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

Comment
To appear at DISC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.77
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST

cs.DC ·2026-08-19 ·Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
theory similarity 0.71
Abstract

Vizing's theorem states that any graph of maximum degree $Δ$ can be properly edge-colored with $Δ+ 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(Δ+ 1)$-edge coloring can be found deterministically in $poly(Δ,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(Δ,\log n)$-round algorithm for $(Δ+ 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.

0.16

Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds

cs.DS cs.DC ·2026-10-12 ·Marc Fuchs, Fabian Kuhn
theory similarity 0.70
Abstract

We give a deterministic distributed algorithm for $(Δ+1)$-coloring an $n$-node graph of maximum degree $Δ$ in $O(\sqrtΔ+\log^* n)$ rounds in both the LOCAL and CONGEST models. More generally, $(°+1)$-list coloring with lists from a color space of size $C\geqΔ+1$ can be solved in $O(\sqrtΔ\log(1+C/Δ)+\log^* n)$ rounds; in CONGEST, we assume $C\leq n^{O(1)}$. The algorithm combines Barenboim's polynomial coloring procedure with arbdefective decompositions, degree reduction, and a short family of hash functions. Using the polynomial procedure in the degree-reduction framework already gives an $O(\sqrtΔ\logΔ+\log^* n)$-round algorithm when $C=O(Δ)$. Hashing adapts the color space to the current degree and removes the logarithmic factor. We prove the existence of the hash family by the probabilistic method and compute it by deterministic exhaustive search, using unrestricted local computation. We also give an explicit variant based on lossless expanders that avoids this search and achieves $O(\sqrtΔ+\log^* n)$ rounds for $C=O(Δ)$.

0.19

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.67
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21

More Efficient Parallel $(Δ+1)$-Edge Coloring

cs.DS ·2026-09-28 ·Jeremy T. Fineman, Seyed Ali Mohammadi
similarity 0.66
Abstract

This paper gives two parallel algorithms for $Δ+1$ edge coloring, where $Δ$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(Δ^3)$ span and $\tilde{O}(m Δ^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}(Δ^2)$ span and $\tilde{O}(m Δ^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(Δ^4)$ span and $\tilde{O}(m Δ^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(Δ)$ improvement on span and $\tilde{O}(Δ^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(Δ^2)$ and $\tilde{O}(Δ^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.

0.06

Streaming Hypergraph Coloring via Palette Sparsification

cs.DM math.COcs.DS ·2026-08-20 ·Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler
theory similarity 0.64
Abstract · 25 pages. This revision merges the original manuscript with independent work by Czumaj, Peng, and Sohler

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $Δ$ with $O(Δ^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $Θ(\sqrt{\log n})$ colors from a palette of size $O(Δ^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $Δ$ for which any deterministic one-pass algorithm requires $\exp(Δ^{Ω(1)})$ colors.

0.37

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

cs.DS ·2026-10-26 ·Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
similarity 0.63
Abstract

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.

0.19

Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates

cs.DS cs.DM ·2026-09-27 ·Ijay Narang, Yukai Tang
similarity 0.63
Abstract

We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamt{á}{č}, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.

0.47