CS Paper Radar

Distributed Near-Equitable Coloring in the LOCAL Model

Amit Nir, David Peleg

cs.DC cs.DS ·submitted 2026-08-10 06:37 UTC · v1

Abstract

For an $n$-vertex graph of maximum degree $Δ$, an equitable $(Δ+1)$-coloring is a proper coloring all of whose color classes have size $σ= n/(Δ+1)$ up to rounding. Known algorithms for relaxations of this target aggregate along a spanning structure, at cost scaling with the diameter $D$. We study near-equitable coloring in the LOCAL model and prove that, for deterministic algorithms, exact balance is inherently global: already on the cycle $C_n$, exact balanced free $3$-coloring requires $Ω(n)$ rounds. More generally, additive imbalance $g$ requires $Ω(n/g)$ rounds, matching a deterministic $O((n/g)\log^* n)$-round algorithm up to the $\log^* n$ factor, and these problems realize a dense family of intermediate deterministic LOCAL complexities $\tildeΘ(n^α)$, $α\in (0,1)$, on cycles. The exact bound is sharp in two further senses: the identifier-universe threshold is exactly $N=n+1$, and the $\log^* n$ gap cannot be closed via faster ruling-set anchors. The bound then extends to twisted fiber products, an explicit family realizing, for every $Δ\ge 3$, every diameter scale from the Moore bound $Θ(\log n/\logΔ)$ up to $Θ(n/Δ)$. Exact equitable $(Δ+1)$-coloring requires $Θ(D)$ rounds deterministically on this family, so exactness costs diameter time already on bounded-degree graphs of logarithmic diameter. In contrast, coarse balance admits local algorithms. On cycles, constant multiplicative equity costs $Θ(\log^* n)$ rounds. On general graphs with large color classes, all class sizes can be kept within $(1\pmη)$ times the average in time independent of the diameter: with palette exactly $Δ+1$ for $Δ\le 2^{\sqrt{\log n}/C}$, and with palette $(1+η)(Δ+1)$ for every $Δ\le n^{1-o(1)}$, the latter in $O(\log n\,(\log\log n)^2)$ rounds.

Comment
54 pages, 5 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

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.78
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

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

cs.DC ·2026-08-19 ·Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
theory similarity 0.74
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.73
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

A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs

cs.CC math.COcs.IT ·2026-11-03 ·Andrew D. Lin
theory similarity 0.69
Abstract

A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once. We give a short and simple proof of a result of [ABSZZ] showing that a properly edge-colored $n$-vertex graph with average degree $Ω(\log n\log\log n)$ always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most $\ell$ and where the total weight of all edges containing a given color $i$ incident to a vertex is at most $Δ$, showing that $Ω_\ell(Δ\log n\log\log n)$ average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for $r\geq 3$, every binary linear $r$-query locally correctable code $E:\mathbb{F}_2^k\rightarrow \mathbb{F}_2^n$ satisfies $k\leq \tilde{O}(n^{1-2/(r-1)})$ by showing a rainbow analogue of the odd $r$-LDC lower bounds of [BHKL25,JM25], closing the gap between the best known lower bounds for odd- and even-query binary linear $r$-LCCs.

0.20

Online Graph Coloring with Random Arrivals

cs.DS cs.DM ·2026-10-16 ·Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.67
Abstract

We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time algorithm that colors any $k$-colorable graph on $n$ vertices with $O(k^3 \log^2 k \log^4 n)$ colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed $k \geq 3$, and is better than a known lower bound of $Ω(\log^{k-1} n)$ colors under adversarial arrivals for all fixed $k \geq 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\widetilde{O}(n^{2/3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\varepsilon}$ for all fixed $\varepsilon > 0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

0.14

New bounds for online coloring three-colorable graphs

cs.DS ·2026-10-30 ·Yaqiao Li
theory similarity 0.67
Abstract

We prove new lower and upper bounds for online coloring of three-colorable graphs, improving classical bounds of Vishwanathan [FOCS'1990] that have stood for more than three decades. For the lower bound against deterministic algorithms, we improve Vishwanathan's $Ω(\log^2n)$ to \(\exp\!\bigl(Ω((\log n)^{1/3}(\log\log n)^{2/3})\bigr)\). For the upper bound of randomized algorithms, we give a randomized algorithm that achieves $O(\sqrt{n})$ improving Vishwanathan's $O(\sqrt{n \log n})$. Technically, for the lower bound construction, we introduce the language of $t$-fold coloring for simpler description of recursive construction, and the notion of post-degree for future control, and use the flexibility of two-sided colors of bipartite graph, constructed using the independent set amplification method of Vishwanathan, as building blocks to ensure three-colorability. The randomized algorithm integrates, in a new way, some of the ideas in offline coloring of Wigderson and Blum with ideas of Vishwanathan in the online setting, such as the degree control from Wigderson, the offline-monochromatic class from Blum, and the anchor-sampling from Vishwanathan and the CBIP algorithm by Lov{á}sz, Saks and Trotter.

0.21

Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing

cs.DM math.COcs.DS ·2026-11-02 ·Rishikesh Gajjala, Arindam Khan
benchmarktheory similarity 0.67
Abstract · 94 pages

We study weighted edge coloring, where each edge of a graph $G$ has a weight in $(0,1]$, and colors are assigned so that the incident weight of each color at every vertex is at most one. The objective is to minimize the number of colors, denoted by $χ'_w(G)$. This generalizes classical edge coloring (all weights are one) and bin packing ($G$ is a star). Two natural lower bounds are the maximum weighted degree $Δ_w(G)$ and the maximum local bin-packing number $\mathrm{bp}(G)$: the maximum, over vertices, of the minimum number of unit bins needed to pack the incident weights. We have $\lceilΔ_w(G)\rceil\le\mathrm{bp}(G)\leχ'_w(G)$. How closely these local lower bounds approximate the global optimum is a longstanding open problem. Our main result establishes an asymptotic weighted analogue of Vizing's theorem: every simple graph admits a coloring using at most $(1+o(1))\mathrm{bp}(G)$ colors. Thus local bin packings can be made globally consistent with asymptotically vanishing relative loss, even in nonbipartite graphs. Our local-to-global rounding framework coordinates feasible local packing distributions into a partial coloring, leaving only $o(\mathrm{bp}(G))$ uncolored weight at every vertex. For bipartite multigraphs, we prove $χ'_w(G)\le(2+o(1))Δ_w(G)$, establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound $χ'_w(G)\le3\lceilΔ_w(G)\rceil$. Both leading coefficients are optimal, giving weighted analogues of the classical Kőnig--Shannon bounds. Further upper and lower bounds show that the classical factor-$3/2$ separation does not persist with the local bin-packing benchmark. We also disprove the exact weighted-degree conjecture of Feige and Singh [ESA'08]. Our upper bounds have polynomial-time algorithms, and their existence statements are formalized in Lean 4.

0.24

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

cs.DS cs.DMmath.CO ·2026-11-10 ·Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.67
Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

0.18