Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model

Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model Amit Nir∗

David Peleg∗

August 5, 2026

arXiv:2608.02920v1 [cs.DC] 3 Aug 2026

Abstract This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost. Let λ ≥ 1 denote the desired failure exponent. For every fixed δ > 0, the first algorithm uses −λ χ = ⌈(2+δ)∆⌉ colors and, with probability at least 1−n p , outputs a proper coloring that  bounds the deviation of every color frequency from n/χ by Oδ (λ + 1)(n/χ) lg n + (λ + 1) lg n . Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every χ > ∆ and gives a one-sided frequency cap controlled by the palette slack χ − ∆. In particular, it uses ∆ + ⌈(∆ + 1)/⌈ln n⌉⌉ colors and caps every used color class by O((λ + 1)(σ lg2 n + lg n)), where σ = n/(∆ + 1). Both algorithms run in O((λ + 1) lg n) rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on δ.

1

Introduction

1.1

Background and Problem

We study distributed algorithms for equitable graph coloring. The problem is governed by two different requirements: properness requires adjacent vertices to use different colors, which can be enforced by local communication, while balance (or equitability), requires that the frequency of each color (i.e., the number of vertices assigned to it) be (almost) equal, which is inherently global. The more relaxed near-equitable coloring problem asks whether these conflicting requirements can be met simultaneously, and at what cost in palette size, frequency discrepancy, and running times. To illustrate why exact balance is a global constraint, consider an anonymous ring Cn and any randomized t-round algorithm on it. By symmetry, all vertices share one output distribution, which properness forces to be non-degenerate, and the outputs of any ⌊n/(2t + 1)⌋ vertices at pairwise distance exceeding 2t are mutually independent, being functions of disjoint portions of the p randomness. The number of such vertices receiving a fixed color therefore fluctuates by order n/t. This suggests that maintaining all frequencies within ±1 of each other, as exact equitability demands, requires coordination at diameter scale, whereas properness alone is a purely local matter. Accordingly, we relax exactness and quantify how closely balance can be approximated without global coordination. (For formal lower bounds see [17].) Let G = (V, E) be a finite simple undirected graph. Denote n = |V |, m = |E|, and let ∆ be the maximum degree. We use D to denote the largest diameter of a connected component of G; thus D ∗

Weizmann Institute of Science. E-mail: {amit.nir,david.peleg}@weizmann.ac.il.

1

remains finite even when G is disconnected. The open neighborhood of a vertex v is denoted by N (v), and deg(v) = |N (v)|. For an integer χ ≥ 1, a χ-coloring is a function ϕ : V → [χ], where [χ] = {1, . . . , χ} is termed the palette. The coloring is proper if ϕ(u) ̸= ϕ(v) for every uv ∈ E. For a color i ∈ [χ], its frequency is f(i) = |{v ∈ V | ϕ(v) = i}|. A color of positive frequency is termed a used color. Denote the ideal frequency associated with the palette by σχ = n/χ, and put σ = n/(∆ + 1). We distinguish three balance notions. A proper coloring is equitable if the frequencies of any two palette colors differ by at most one; equivalently, every frequency belongs to {⌊n/χ⌋, ⌈n/χ⌉}. For B ≥ 0, it is B-additively balanced if |f(i) − σχ | ≤ B for every palette color i. For 0 < η ≤ 1, it is η-relatively balanced if (1 − η)σχ ≤ f(i) ≤ (1 + η)σχ

for every i ∈ [χ].

These two relaxations are referred to as near-equitable. Finally, a proper coloring is F -upper-balanced if every used color has frequency at most F . An upper-balanced coloring need not be near-equitable, since it may contain singleton color classes. The classical Hajnal–Szemerédi theorem ensures that an equitable χ-coloring exists for every χ ≥ ∆ + 1 [9]; polynomial-time centralized constructions are also known [13]. The current paper addresses a different issue, namely, obtaining explicit frequency guarantees quickly in bandwidthlimited distributed networks.

1.2

Distributed Models and Conventions

We work in the synchronous CONGEST model. The communication network is G, each vertex hosts a processor driven by a global clock, and in every round each endpoint of an edge may send an O(lg n)-bit message to the other endpoint. The algorithms assume common knowledge of n, ∆, the palette size χ, and their accuracy and failure parameters. The failure exponent λ ≥ 1 is an input parameter; the phrase with high probability (w.h.p.) means probability at least 1 − n−λ for the specified value of λ. We use lg for the base-2 logarithm and ln for the natural logarithm. All probability statements concern the internal random choices of the algorithms. The exact value of n can be replaced by a common estimate N satisfying n ≤ N ≤ nK for a fixed constant K. Specifically, replacing n by N in stopping times and failure parameters changes the asymptotic round bounds by at most a constant factor and can only decrease the stated failure probabilities. The same replacement enters the frequency parameters as well: the quantities Rsamp , Bχ , T , Rprop and Ψp,χ defined below are then computed with N in place of n, and since N ≤ nK , each of them grows by at most the constant factor K; hence all stated deviation bounds and frequency caps degrade by at most a constant factor as well. To avoid cumbersome notation, the presentation assumes that n itself is known. When ∆ = 0, assigning the single color 1 to every vertex gives an equitable coloring in zero rounds. Hence we assume ∆ ≥ 1 hereafter. No connectedness assumption is made.

1.3

Our Contributions

Our earlier work [16] obtains several palette–frequency tradeoffs by maintaining global color counts and assigning global color quotas. In the CONGEST model, it achieved (1) a coloring with at most 2(∆ + 1) colors, frequency range [σ/2, σ] and time O(lg ∆ (D + ∆ + lg5 lg n)), (2) for every integer k ≥ 1, a coloring with at most (1 + 1/k)(∆ + 1) colors, frequency range [σ/3, 2kσ] and time O(D + ∆ + lg5 lg n), and (3) a coloring with exact (∆ + 1)-color palette, frequency range 2

[σ/2, 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉] and time O((D + ∆) lg n lg ∆). These CONGEST running times thus retain an additive D + ∆ term. The governing question here is which guarantees survive when this global coordination cost is avoided. The first procedure, termed Sampler_Balance, invokes the distributed coloring sampler of Feng, Hayes, and Yin [5] as a black box. With χ = ⌈(2+δ)∆⌉, it samples a coloring whose probability law is close to the uniform distribution on proper colorings. The contribution lies in the frequency analysis: a Dobrushin/self-bounding argument proves that all color frequencies concentrate simultaneously under the target distribution, and total-variation distance transfers this event to the sampler output. Hence the procedure controls a global statistic without computing it. Theorem A (informal). For every fixed δ > 0 and every λ ≥ 1, procedure Sampler_Balance computes, with probability at least 1 − n−λ , a proper coloring with χ = ⌈(2 + δ)∆⌉ colors satisfying r  n n = Oδ f(i) − (λ + 1) lg n + (λ + 1) lg n simultaneously for all i ∈ [χ]. χ χ It runs in Oδ ((λ+1) lg n) CONGEST rounds, with no dependence on the diameter D. (See Theorem 3.3.) The second procedure, termed Slack_Greedy, uses an elementary parallel random-greedy process. Every uncolored vertex proposes a locally available color, and a proposal is accepted when it has no simultaneous conflict. The excess s = χ − ∆ is termed the palette slack. The same slack that pays for local progress also limits the proposal load of each color. This yields an upper-balanced coloring for every χ > ∆, including a palette arbitrarily close to ∆ + 1. The price is that our analysis provides no lower-frequency guarantee; whether the algorithm itself satisfies one is an open question (see Remark 4.6 and Section 5). Theorem B (informal). For every integer χ > ∆ and every λ ≥ 1, procedure Slack_Greedy computes, with probability at least 1 − n−λ , a proper coloring using at most χ colors in which every used color has frequency at most     n lg n min n, O (λ + 1) + lg n . χ−∆ In particular, with χ = ∆ + ⌈(∆ + 1)/⌈ln n⌉⌉ colors, the cap is min{n, O((λ + 1)(σ lg2 n + lg n))}, where σ = n/(∆ + 1). It runs in O((λ + 1) lg n) CONGEST rounds, with no dependence on the diameter D. (See Theorem 4.5 and Corollaries 4.7 and 4.8.) Table 1 summarizes the two tradeoffs. The exact frequency parameters are defined in Theorems 3.3 and 4.5. The near-exact-palette endpoint of Slack_Greedy deserves one qualification. Its exact cap always includes the deterministic minimum with n. For fixed λ, the asymptotic expression improves on the trivial cap only when ∆ is larger than a sufficiently large constant multiple of lg2 n, and it is o(n) when ∆/ lg2 n tends to infinity. Thus the endpoint is most informative in the moderate- and high-degree regimes. Two robustness remarks are in order. First, exact knowledge of ∆ is not needed: if the vertices ˆ ≥ ∆ and the parameters below are computed from ∆, ˆ then all are given a common upper bound ∆ ˆ guarantees continue to hold with ∆ replaced by ∆ throughout. (For the first algorithm this holds ˆ ≥ (2 + δ)∆ still meets the sampler’s threshold; for the second, because the true because χ ≥ (2 + δ)∆ ˆ Second, neither conflict and proposal probabilities are only smaller than the ones computed from ∆.) algorithm ever transmits a vertex identifier: messages carry only colors, proposals, and activation bits. Hence both algorithms run unchanged in anonymous networks with port numbering, given common knowledge of the parameters.

3

Table 1: Summary of the two procedures, preceded, for comparison, by the three tradeoff points (1)–(3) of the companion work [16] listed above (whose running times carry an additive diameter term) . The failure probability is at most n−λ . Procedure

Palette

Frequency guarantee

CONGEST rounds

Sequential time

[16] (1)

2(∆ + 1)

[16] (3)

(1 + 1/k)(∆ + 1), k≥1 ∆+1

O(lg ∆ (D + ∆ + lg5 lg n)) O(D + ∆ + lg5 lg n)

–

[16] (2)

Two-sided range [σ/2, σ] Two-sided range [σ/3, 2kσ] Two-sided range [σ/2, 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉]

O((D + ∆) lg n lg ∆)

–

Sampler_Balance

⌈(2 + δ)∆⌉

Oδ ((λ + 1) lg n)

Oδ ((m + n)(λ + 1) lg n)

Slack_Greedy

Every χ > ∆

Two-sided additive balance; relative balance under Condition (17) One-sided cap Ψp,χ ; for the near-exact palette, see Corollary 4.8

O((λ + 1) lg n)

O((m + n)(λ + 1) lg n) (expected)

1.4

–

Relation to Previous Work

Equitable coloring is introduced by Meyer [15]; the existence theory culminates in the Hajnal– Szemerédi theorem and its algorithmic versions [9, 13]. Parallel balanced coloring is also studied as a practical load-balancing problem on shared-memory and manycore machines [14]. Those algorithms and objectives differ from the bandwidth-limited message-passing guarantees considered here. The local symmetry-breaking literature supplies fast proper colorings but does not ordinarily constrain global color-class sizes. In particular, the elementary randomized (∆ + 1)-coloring process is analyzed by Johansson [12], and faster LOCAL-model algorithms are known for (∆ + 1)-coloring [11]. In the CONGEST model itself, Halldórsson, Kuhn, Maus, and Tonoyan solve (∆ + 1)-list coloring in O(lg5 lg n) rounds w.h.p. [10]. Measured against this properness-only baseline, the O((λ + 1) lg n) running times obtained here are the price of the added frequency guarantees. Distributed defective and frugal colorings impose local restrictions on monochromatic degrees or on repeated colors in neighborhoods [2, 6]; these restrictions are different from the global frequency bounds studied herein. For the first result, Feng, Hayes, and Yin prove rapid mixing of the Lazy Local Metropolis chain above the (2 + δ)∆ threshold [5]. Fischer and Ghaffari independently obtain the same threshold using Local Glauber dynamics [7]. The Sampler_Balance procedure invokes the former chain; the latter result provides independent context for the threshold. Below the 2∆ threshold, the best known distributed sampler is the distributed flip dynamics of Carlson, Frishberg, and Vigoda [1], which handles χ > (11/6 − δ0 )∆ colors for a fixed δ0 > 0 but requires O(n lg n) rounds and leaves the stationary distribution unclear. Thus the palette size of Sampler_Balance reflects the current reach of O(lg n)-round distributed sampling, rather than a limitation of the frequency analysis. The frequency analysis uses Paulin’s concentration inequality for self-bounding functions under Dobrushin dependence [18]. The rest of the paper is organized as follows. Section 2 states the probabilistic tools. Section 3 presents the sampling-based algorithm and proves its two-sided frequency guarantee. Section 4 presents the coordination-free greedy algorithm and derives its palette–frequency tradeoffs. Section 5 discusses the limitations of the two approaches. 4

2

Probabilistic Tools

This section reviews the two concentration mechanisms used in the paper. The first concerns dependent random vectors satisfying a Dobrushin contraction condition. The second controls an adaptively exposed sum of Bernoulli variables.

2.1

Total-Variation Distance

For two probability distributions ν and ν ′ on a finite space Ω, their total-variation distance is TVD(ν, ν ′ ) =

1X |ν(ω) − ν ′ (ω)| = max |ν(E) − ν ′ (E)|. E⊆Ω 2

(1)

ω∈Ω

The following immediate consequence is the only property used hereafter. Fact 2.1. If an event E satisfies Pν ′ [E] ≥ 1 − β, then Pν [E] ≥ 1 − β − TVD(ν, ν ′ ).

2.2

Dobrushin Dependence and Self-Bounding Concentration

Let X = (Xv )v∈V be a random vector on a finite product space. Denote by X−v = (Xu )u̸=v the vector obtained by deleting coordinate v. For a random variable Y , the notation L(Y ) denotes its probability law. For every vertex v, fix a version of the conditional kernel of Xv given X−v . A nonnegative matrix A = (Avu )v,u∈V with zero diagonal is termed a Dobrushin interdependence matrix for X if, for every v and every two boundary configurations x−v and y−v in the domain of these kernels, X TVD(L(Xv | X−v = x−v ), L(Xv | X−v = y−v )) ≤ Avu 1{xu ̸= yu }. (2) u̸=v

Here 1{S} is the indicator of a statement S, namely, it equals 1 when S holds and 0 otherwise. Thus Avu bounds the effect of coordinate u on the conditional distribution at coordinate v. The qualification concerning a fixed kernel matters only on boundary configurations of probability zero, where conditioning alone does not determine a unique distribution. We use the maximum row and column sums X X ∥A∥∞ = max Avu , ∥A∥1 = max Avu . v

u

u

v

The inequality ∥A∥1 < 1 is the Dobrushin contraction condition employed below. A nonnegative function g on the same product space is termed (1, 0)-∗-self-bounding if there are coordinate coefficients av (x) ∈ [0, 1] such that, for every two configurations x and y, X X g(x) − g(y) ≤ av (x), av (x) ≤ g(x). (3) v∈V xv ̸=yv

v∈V

Intuitively, each changed coordinate can account for at most one unit of decrease in g, and the total available charge is bounded by the current value of g. We use the following specialization of Paulin’s concentration inequality [18].

5

Fact 2.2. [18, Corollary 3.2] Let A be a Dobrushin interdependence matrix for X such that ∥A∥1 < 1 and ∥A∥∞ ≤ 1. Let g be a nonnegative (1, 0)-∗-self-bounding function, and put Γ = 1 − ∥A∥1 . Then, for every t ≥ 0,   Γt2 , (4) P[g(X) ≥ E[g(X)] + t] ≤ exp − 2(E[g(X)] + t)   Γt2 P[g(X) ≤ E[g(X)] − t] ≤ exp − . (5) 8E[g(X)] The lower-tail inequality is Part (3) of the cited corollary. A (1, 0)-∗-self-bounding function is also weakly (1, 0)-∗-self-bounding, and its value changes by at most one when a single coordinate is changed. Moreover, the constant ac in [18, Corollary 3.2] satisfies ac < 0.286. Hence the additional condition 1 ≥ ac (1 − ∥A∥1 ) required there holds automatically.

2.3

Adaptive Bernoulli Sums

The frequency analysis of Slack_Greedy uses a conditional form of the Bernstein–Chernoff bound. The following statement records the standard moment-generating-function estimate that permits adaptive trials. It follows from the stochastic domination of (Yj )j by a sequence of independent Bernoulli(qj ) trials, to which the usual Bernstein–Chernoff bound applies; see Doerr [4, Section 1.10.2] for the domination step and [3, Chapter 1] for the Chernoff computation. Alternatively, it is a special case of Freedman’s martingale inequality [8]. Fact 2.3. Let Y1 , . . . , YN ∈ {0, 1} be adapted to a filtration F0 , . . . , FN . Suppose that deterministic numbers q1 , . . . , qN ∈ [0, 1] satisfy P[Yj = 1 | Fj−1 ] ≤ qj Denote µ =

almost surely for every j ∈ [N ].

PN

j=1 qj . Then, for every ϑ ≥ 0 and every x ≥ 0,





Eexpϑ

N X


Yj  ≤ exp (eϑ − 1)µ ,

(6)

j=1

  N X p 2x  P Yj > µ + 2µx + ≤ e−x . 3

(7)

j=1

Note that Fact 2.3 requires no independence between the variables Yj . It suffices to bound each success probability conditioned on the information revealed earlier.

3

Near-Equitable Coloring by Local Sampling

The first tradeoff point retains a two-sided frequency guarantee and removes global coordination by enlarging the palette to about 2∆. Its algorithmic ingredient is the Lazy Local Metropolis sampler of Feng, Hayes, and Yin [5]. We first state the transition rule and the black-box mixing guarantee precisely. We then prove frequency concentration under the uniform proper-coloring measure and transfer the resulting event to the sampler output.

6

3.1

The Lazy Local Metropolis Sampler

For an integer χ ≥ 1, let Ωχ = [χ]V . Denote by πχ the uniform distribution over the proper χ-colorings of G, viewed as a distribution on Ωχ . We now describe one step of the Lazy Local Metropolis chain. Let Xt ∈ Ωχ be the current coloring and put pδ = min{δ/3, 1/2}. Every vertex becomes active independently with probability pδ . Each active vertex v chooses a proposal ct (v) uniformly from [χ] and sends the pair (Xt (v), ct (v)) to its neighbors. An edge uv with two active endpoints is said to pass if ct (u) ̸= ct (v),

ct (u) ̸= Xt (v),

Xt (u) ̸= ct (v).

(8)

An edge uv with active endpoint v and inactive endpoint u passes if ct (v) ̸= Xt (u).

(9)

An active vertex adopts its proposal only if every incident edge passes. Every other vertex retains its current color. Note that Eq. (8) contains three distinct checks; all three are part of the chain analyzed in [5]. The chain may be initialized at an arbitrary χ-coloring, which need not be proper. Every step maps a total coloring to a total coloring, although intermediate colorings need not be proper. The sampling property required here is the following result of Feng, Hayes, and Yin [5]. Fact 3.1. [5] For every fixed δ > 0, there is a constant Cδ > 0 with the following property. Let
χ ≥ (2 + δ)∆ and 0 < ζ < 1. Starting from any X0 ∈ Ωχ , after at most Cδ ln n + ln(1/ζ) rounds, b whose distribution ν satisfies TVD(ν, πχ ) ≤ ζ. the Lazy Local Metropolis algorithm returns a coloring X b is improper] ≤ ζ. Every message contains O(lg n) bits. In particular, P[X Fischer and Ghaffari [7] obtain the same χ > 2∆ threshold for a different chain, namely, Local Glauber dynamics.

3.2

Procedure Sampler_Balance

Fix δ > 0 and put

n . χ Procedure Sampler_Balance starts from an arbitrary total χ-coloring and executes the sampler with target total-variation error ζ = n−(λ+4) . Its only persistent local state is the current color. At the end, one additional neighbor round verifies properness. The complete procedure is given in Algorithm 1. χ = ⌈(2 + δ)∆⌉,

σχ =

Algorithm 1: Procedure Sampler_Balance Input: Graph G = (V, E), constants δ > 0 and λ ≥ 1. Output: A proper χ-coloring, or local failure. 1 χ ← ⌈(2 + δ)∆⌉ and ζ ← n−(λ+4) ; 2 Start from an arbitrary total χ-coloring of V ; 3 Run the Lazy Local Metropolis algorithm for Cδ (ln n + ln(1/ζ)) rounds, where Cδ is the constant from Fact 3.1; 4 Every vertex sends its final color to its neighbors; 5 Every endpoint of a monochromatic edge declares local failure; all other vertices output their final colors; 7

If a failure is declared anywhere, the distributed execution is considered unsuccessful. The procedure requires no global failure-detection mechanism: the theorem below concerns the event that no vertex declares failure.

3.3

Frequency Concentration under the Uniform Measure

We next analyze a proper coloring drawn exactly from πχ . Put α=

∆ , χ−∆

γ = 1 − α.

(10)

The choice of χ gives 1 δ < 1, γ≥ > 0. 1+δ 1+δ The main analytic ingredient is the following concentration statement. α≤

Lemma 3.2. Let X ∼ πχ . For every i ∈ [χ], define Φi (x) = |{v ∈ V | xv = i}|,

x ∈ Ωχ .

Then E[Φi (X)] = σχ , and, for every t ≥ 0,   γt2 , P[Φi (X) ≥ σχ + t] ≤ exp − 2(σχ + t)   γt2 P[Φi (X) ≤ σχ − t] ≤ exp − . 8σχ

(11) (12)

Proof. Fix a color i. We first establish a Dobrushin interdependence bound. For every boundary configuration x−v , including configurations of probability zero, define the conditional kernel at v to be uniform over Pv (x) = [χ] \ {xu | u ∈ N (v)}. (13) This palette is nonempty since χ > deg(v). On every feasible boundary configuration, Eq. (13) is exactly the conditional law of Xv under πχ . Consider first two boundary configurations that differ only at a coordinate u. If uv ∈ / E, their kernels at v are identical. If uv ∈ E, the two available palettes differ by at most one deletion and one insertion. Both palettes have size at least χ − deg(v). A direct comparison of the two uniform distributions therefore gives total-variation distance at most 1/(χ − deg(v)). Indeed, if the two palettes coincide, the distance is zero. If they are Q ∪ {a} and Q ∪ {b} with a ̸= b and |Q| = k − 1 (one deletion and one insertion), the distance is 1/k; if one is Q and the other Q ∪ {b} with |Q| = k, the distance is 1/(k + 1). In every case the distance is at most one over the smaller palette size, which is at least χ − deg(v). Now consider arbitrary boundary configurations x−v and y−v . Change their differing coordinates one at a time. Applying the preceding single-coordinate estimate at every step and the triangle inequality for total-variation distance yields Eq. (2) for the matrix ( 1/(χ − deg(v)), uv ∈ E, Avu = 0, uv ∈ / E.

8

Its maximum row and column sums satisfy deg(v) ∆ ≤ , χ − deg(v) χ−∆ X 1 ∆ ∥A∥1 = max ≤ . u χ − deg(v) χ−∆

∥A∥∞ = max v

v∈N (u)

Thus both norms are at most α < 1. We next verify the self-bounding property. For a configuration x = (xv )v∈V , set av (x) = 1{xv = i}. For every x and y, X X Φi (x) − Φi (y) ≤ av (x), av (x) = Φi (x). v∈V xv ̸=yv

v∈V

Indeed, every occurrence of color i lost in passing from x to y is charged to its changed coordinate. In more detail, write Sx = {v ∈ V | xv = i}, so that Φi (x) = |Sx | and av (x) = 1{v ∈ Sx }. Then Φi (x) − Φi (y) ≤ |Sx \ Sy |, and every v ∈ Sx \ Sy satisfies xv = i ̸= yv , so it contributes a v (x) = 1 to the sum over the changed coordinates. The second relation holds with equality, since P v av (x) = |Sx | = Φi (x). Hence Φi is (1, 0)-∗-self-bounding. Finally, color-name permutations preserve πχ . The random variables Φ1 (X), . . . , Φχ (X) therefore have the same mean, and their sum is always n. It follows that E[Φi (X)] = n/χ = σχ . Applying Fact 2.2 with 1 − ∥A∥1 ≥ γ proves Eqs. (11) and (12). We remark that changing one coordinate changes Φi by at most one, so a bounded-differences √ inequality under the Dobrushin condition would bound the deviation of Φi by O( n lg n) w.h.p., the number n of coordinates. That bound is informative only when √ variance proxy being the p n lg n ≪ σχ , i.e., when ∆ ≪ n/ lg n. The self-bounding form replaces the ambient dimension n by the mean σχ in the variance proxy, which is what extends the useful range of Theorem 3.3 to ∆ ≪ n/ lg n (cf. Condition (17)). To cover every color simultaneously, define s 8σχ Rsamp 2Rsamp Rsamp = (λ + 4) ln n + ln(2χ), Bχ = + . (14) γ γ

3.4

Main Sampling Guarantee

We obtain the following diameter-independent two-sided guarantee. Theorem 3.3. Fix δ > 0 and λ ≥ 1, let n ≥ 2 (as implied by the standing assumption ∆ ≥ 1), and let χ = ⌈(2 + δ)∆⌉. (a) Algorithm 1 computes, with probability at least 1−n−λ , a proper Bχ -additively balanced χ-coloring. More explicitly, every i ∈ [χ] satisfies max{0, σχ − Bχ } ≤ f(i) ≤ σχ + Bχ .

(15)

In particular, n f(i) − = Oδ χ

r  n (λ + 1) lg n + (λ + 1) lg n χ

simultaneously for all colors i ∈ [χ].

9

(16)

(b) Fix 0 < η ≤ 1. If σχ ≥

8Rsamp , γη 2

(17)

then, with the same probability, the output is η-relatively balanced. The running times are Oδ ((m + n)(λ + 1) lg n) sequentially and Oδ ((λ + 1) lg n) in the CONGEST model. Proof. p We start with Part (a). Let X ∼ πχ and fix a color i. Put r = Rsamp /γ. By Eq. (14), Bχ = 8σχ r + 2r. The lower-tail exponent in Eq. (12) is at least γBχ2 /(8σχ ) ≥ Rsamp . For the upper tail, a direct calculation gives p Bχ2 − 2r(σχ + Bχ ) = 6σχ r + 2r 8σχ r ≥ 0. Hence the exponent in Eq. (11) is also at least Rsamp . A union bound over the two tails and all χ colors shows that every color satisfies Eq. (15) with probability at least 1 − 2χe−Rsamp = 1 − n−(λ+4) under πχ . Let Eadd denote the explicit event in Eq. (15). This event is well-defined without invoking b be the output of the sampler and let ν = L(X). b asymptotic notation. Let X Fact 3.1 gives −(λ+4) TVD(ν, πχ ) ≤ n . Since every coloring in the support of πχ is proper, Fact 2.1 gives b is proper and Eadd holds] ≥ 1 − 2n−(λ+4) ≥ 1 − n−λ (using n ≥ 2). Pν [X This proves the explicit claim. Since γ ≥ δ/(1 + δ) and Rsamp = Oδ ((λ + 1) lg n), Eq. (16) follows deterministically from Eq. (14). Let us now prove Part (b). Apply Eqs. (11) and (12) with t = ησχ . Since 0 < η ≤ 1, the upper-tail exponent is at least γη 2 σχ /4, and the lower-tail exponent equals γη 2 σχ /8. Condition (17) makes both exponents at least Rsamp . The same union bound and total-variation transfer prove the relative guarantee. It remains to account for the running times. Fact 3.1 gives Oδ ((λ + 1) lg n) sampler rounds, and the final verification adds one round. A sequential simulation processes the n activation/proposal choices and scans the m edges in every round, yielding worst-case time Oδ ((m + n)(λ + 1) lg n), since each proposal is drawn uniformly from [χ] with no rejection step. This completes the proof. Theorem 3.3 should be considered in three regimes. The upper bound in Eq. (15) is informative whenever σχ + Bχ < n. The lower bound — and with it the two-sided additive guarantee — is informative exactly when Bχ < σχ , which holds if and only if σχ = Ωδ ((λ + 1) lg n); up to the constant, this is Condition (17) with constant η. Below this load, max{0, σχ − Bχ } = 0 and the lower half of Eq. (15) degenerates to the trivial bound f(i) ≥ 0. Finally, Condition (17) upgrades the additive guarantee to η-relative balance. Thus Condition (17) delineated, essentially, the regime in which a two-sided guarantee is available at all. We remark that under the target distribution itself, the deviation in Eq. (16) is essentially best possible for this palette. Consider, for instance, the graph consisting of n/(∆ + 1) disjoint copies of K∆+1 . Under πχ the cliques are colored independently, so each frequency Φi (X) is a Binomial(n/(∆ + 1), (∆ + 1)/χ) variable with mean σχ and variance Θ(σχ ); already a single color √ deviates by Ω( σχ ) with constant probability, and a routine second-moment computation over the p χ colors raises this to Ω( σχ lg χ) for the maximal deviation (when lg χ = O(σχ )). Hence the first term of Eq. (16) is necessary up to the dependence on λ and the gap between lg n and lg χ. 10

4

Coordination-Free Coloring with Palette Slack

The second tradeoff point brings the palette arbitrarily close to ∆ + 1 and retains a diameterindependent running time. The price is a one-sided guarantee: every used color class is capped, but small classes are not prevented. The algorithm requires only activations, locally available colors, and neighbor conflict tests. Intuitively, palette slack serves two roles. It reduces the probability that a proposal conflicts with a neighbor, and it reduces the maximum conditional probability of proposing any fixed color. More formally, these two effects yield the progress and proposal-load bounds below.

4.1

Procedure Slack_Greedy

Fix an integer χ > ∆ whose color identifiers use O(lg n) bits, and denote the palette slack by s = χ − ∆. Set n χ o , p = min 1, 2∆ and define the predetermined iteration count

θ =1−p+

p2 ∆ , χ

(18)



 (λ + 3) ln n T = Tp,χ = . ln(1/θ)

(19)

The choice of p in Eq. (18) is the minimizer of θ = 1 − p + p2 ∆/χ over p ∈ [0, 1], balancing the activation rate against the conflict rate. If χ < 2∆, then p = χ/(2∆) and θ = 1 − χ/(4∆) < 3/4. If χ ≥ 2∆, then p = 1 and θ = ∆/χ ≤ 1/2. Consequently, T = O((λ + 1) lg n)

for every χ > ∆.

(20)

At the beginning of an iteration, an uncolored vertex deletes the colors already used by its colored neighbors. Active uncolored vertices then propose colors in parallel. A proposal is accepted exactly when no active uncolored neighbor makes the same proposal. All acceptances within an iteration are simultaneous. The number of iterations is fixed in advance, so no global termination test or global color counter is required. The formal procedure is given in Algorithm 2. Algorithm 2: Procedure Slack_Greedy Input: Graph G = (V, E), palette size χ > ∆, and failure exponent λ ≥ 1. Output: A proper coloring, or local failure. 1 Compute p and T from Eqs. (18) and (19); set U ← V ; 2 for t = 1, . . . , T do 3 Every v ∈ U becomes active independently with probability p; 4 foreach active v ∈ U in parallel do 5 Pt (v) ← [χ] \ {ϕ(u) | u ∈ N (v) \ U }; 6 Choose ct (v) ∈ Pt (v) uniformly and send it to every neighbor; 7

8

Every active v ∈ U whose proposal differs from all proposals of active vertices in N (v) ∩ U sets ϕ(v) ← ct (v); Every newly colored vertex sends its color to its neighbors and removes itself from U ;

9 Every vertex in U declares local failure; every other vertex outputs its color;

11

4.2

Progress and Termination

We first establish the properness invariant and the one-iteration progress bound. Lemma 4.1. At every iteration, the current partial coloring is proper. Moreover, for every uncolored vertex v and every execution history up to the beginning of the iteration, P[v remains uncolored after the iteration | history] ≤ θ. Proof. Let U be the uncolored set at the beginning of the iteration. Denote degU (v) = |N (v) ∩ U | and av = |Pt (v)|. At most ∆ − degU (v) colored neighbors exclude colors. Hence av ≥ χ − (∆ − degU (v)) = s + degU (v).

(21)

An active vertex proposes a color unused by its colored neighbors. If two adjacent active vertices make the same proposal, neither is accepted. Therefore simultaneous acceptance preserves properness. Condition on the history and on v being active. For an uncolored neighbor u of v, let Econfl (u) be the event that u is active and ct (u) = ct (v). Fresh activations and proposals are mutually independent, so Eq. (21) gives X P[Econfl (u) | history, v active] = P[u is active] · P[ct (v) = i] · P[ct (u) = i] i∈Pt (u)∩Pt (v)

= p

X i∈Pt (u)∩Pt (v)

1 p p . ≤ ≤ au av av s + degU (v)

(22)

A union bound over the uncolored neighbors yields P[v has a conflict | history, v active] ≤

p degU (v) p∆ p∆ = . ≤ s + degU (v) s+∆ χ

The second inequality holds because x/(s+x) is increasing for x ≥ 0. Thus v is colored with probability at least p(1 − p∆/χ), and the probability that it remains uncolored is at most 1 − p + p2 ∆/χ = θ. The progress bound can be multiplied across iterations without an independence assumption: one conditions successively on the complete history at the beginning of each iteration. It follows that a fixed vertex remains uncolored after all T iterations with probability at most θT ≤ n−(λ+3) . A union bound now gives the following termination guarantee. Corollary 4.2. Algorithm 2 colors every vertex with probability at least 1 − n−(λ+2) .

4.3

Frequency Analysis

An accepted proposal of color i contributes one vertex to f(i), whereas a rejected proposal contributes nothing. Hence the total number of proposals of i is an upper bound on its final frequency. Define µp,χ =

pnT , χ−∆

Rprop = (λ + 3) ln n + ln χ,

(23)

and put    p 2Rprop Ψp,χ = min n, µp,χ + 2µp,χ Rprop + . 3 The proposal process gives the following simultaneous cap. 12

(24)

Lemma 4.3. With probability at least 1 − n−(λ+3) , every color used by Algorithm 2 has frequency at most Ψp,χ . Proof. Fix a color i, and let Zi denote its total number of proposals, including rejected proposals. We define the filtration used to expose these proposals. Order the nT potential vertex–iteration trials lexicographically by iteration and by an arbitrary fixed vertex order. At the start of an iteration, the current uncolored set and every available palette are already determined by earlier iterations. Within that iteration, expose the fresh activation and, when active, the proposal of each vertex in the fixed order. Acceptance decisions are determined only after all proposals of the iteration have been exposed, and are added to the history before the next iteration begins. A trial corresponding to an already colored vertex is padded with the value zero. Let Yj indicate that trial j proposes color i, and let Fj contain the information exposed through that trial together with all acceptance decisions of completed iterations. Conditioned on Fj−1 , the probability that trial j, corresponding to a vertex v, proposes i is either zero or p/|Pt (v)| ≤ p/(χ−∆). Thus Fact 2.3 applies with qj = p/(χ − ∆) for all nT trials and total budget µp,χ . It follows that   p 2Rprop P Zi > µp,χ + 2µp,χ Rprop + ≤ e−Rprop . 3 Every accepted proposal of i is counted by Zi , so f(i) ≤ Zi . We also have the deterministic bound f(i) ≤ n. Equation (24) and a union bound over all palette colors give P[some color i satisfies f(i) > Ψp,χ ] ≤ χe−Rprop = n−(λ+3) . The lemma follows. Remark 4.4 (The cost of a deterministic proposal budget). The budget µp,χ charges every vertex a proposal at every one of the T iterations. In expectation, far fewer proposals occur: by Lemma 4.1, a vertex is still uncolored at the start of iteration t with probability at most θt−1 , so the total number Zi of proposals of a fixed color i satisfies E[Zi ] ≤

p X t−1 2n pn ≤ , nθ = χ−∆ (χ − ∆)(1 − θ) χ−∆ t≥1

since 1 − θ = p(1 − p∆/χ) ≥ p/2. Thus E[Zi ] = O(n/(χ − ∆)), independently of T — a factor Θ(pT ) below µp,χ . The factor T in Ψp,χ is therefore an artifact of the deterministic budget: Fact 2.3 requires deterministic bounds qj , whereas the geometric decay of the uncolored set is a random event that the conditioning has already exposed, so the analysis cannot take credit for it. Converting this expectation benchmark into a high-probability cap — say, P via martingale inequalities with random predictable variance, combined with concentration of t |Ut | — would improve the caps of Corollaries 4.7 and 4.8 by a Θ(lg n) factor. We leave this as an open question.

4.4

Main Guarantee and Tradeoff Points

Combining progress with the proposal cap yields the general guarantee. Theorem 4.5. Let n ≥ 2, λ ≥ 1, and let χ > ∆ be an integer whose color identifiers use O(lg n) bits. Algorithm 2 computes, with probability at least 1 − n−λ , a proper Ψp,χ -upper-balanced coloring using at most χ colors. Its expected sequential running time is O((m + n)T ), and its running time in the CONGEST model is O(T ), where T = O((λ + 1) lg n). 13

Proof. Corollary 4.2 gives proper completion with failure probability at most n−(λ+2) , and Lemma 4.3 gives the simultaneous cap with failure probability at most n−(λ+3) . For n ≥ 2, their sum is at most n−λ . Every iteration uses one neighbor round for proposals and one for acceptance announcements. Each message contains an activation bit or a color identifier and therefore uses O(lg n) bits. No global termination test is required. For the sequential simulation, store the distinct colors of the already colored neighbors of v in a hash table. Repeatedly draw a uniform color from [χ] until a color outside the table is obtained. This returns a uniform member of Pt (v). If the table contains r ≤ deg(v) colors, the expected number of draws is χ r =1+ ≤ r + 1 ≤ deg(v) + 1. χ−r χ−r Constructing the table and processing all conflicts and announcements takes expected O(deg(v) + 1) time at v per iteration. Summing over all vertices gives expected O(m + n) time per iteration. The theorem follows. Remark 4.6 (Balance in expectation). Algorithm 2 treats the palette symmetrically: available palettes are complements of neighbor colors, proposals are uniform, and acceptance is a pure equality test. Hence relabeling the colors by any permutation π of [χ] maps executions to equally likely executions whose colorings are related by π, so π ◦ ϕ and ϕ have the same law. Consequently, all palette colors have the same expected frequency, E[f(i)] =

n − n−(λ+2) n − E[|UT |] ≥ χ χ

for every i ∈ [χ],

where UT is the uncolored set at termination (the estimate uses E[|UT |] ≤ n · θT ≤ n−(λ+2) ). The one-sidedness of Theorem 4.5 thus reflects the absence of a concentration argument below the mean, not any systematic imbalance of the process itself. We next express the general result in terms of a fractional palette slack. Corollary 4.7. Fix 0 < ρ ≤ 1 and put χ = ∆ + ⌈ρ(∆ + 1)⌉. With probability at least 1 − n−λ , Algorithm 2 computes a proper upper-balanced coloring with χ ≤ (1 + ρ)(∆ + 1) colors and frequency cap    σ lg n O (λ + 1) + lg n . ρ It runs in O((λ + 1) lg n) rounds in the CONGEST model and in expected O((m + n)(λ + 1) lg n) sequential time. Proof. The palette slack satisfies s ≥ ρ(∆ + 1). Equations (20) and (23) give   nT (λ + 1)σ lg n µp,χ ≤ =O , Rprop = O((λ + 1) lg n). ρ(∆ + 1) ρ p Using 2µp,χ Rprop ≤ µp,χ + Rprop /2 in Eq. (24) proves the claim. As in Eq. (24), the cap of Corollary 4.7 should be read together with the deterministic bound f(i) ≤ n, which dominates unless ∆ exceeds a constant multiple of (λ + 1) lg n/ρ. The following endpoint lets the fractional slack vanish with n.

14

Corollary 4.8. Let n ≥ 3 and L = ⌈ln n⌉. There is an absolute constant C0 > 0 such that, with probability at least 1 − n−λ , Algorithm 2 computes a proper coloring with     ∆+1 1 χ=∆+ ≤ 1+ (∆ + 1) L L colors and  f(i) ≤ min n, C0 (λ + 1)(σ lg2 n + lg n)

for every used color i.

Its expected sequential running time is O((m + n)(λ + 1) lg n), and its running time in the CONGEST model is O((λ + 1) lg n). Proof. Here s = χ − ∆ ≥ (∆ + 1)/L. Hence pnT nT L ≤ = σT L = O((λ + 1)σ lg2 n). s ∆+1 √ Also Rprop = O((λ + 1) lg n). Substitution in Eq. (24), together with 2µR ≤ µ + R/2, gives the stated absolute constant C0 . The palette and running-time claims follow from the definitions and Theorem 4.5. µp,χ =

For fixed λ, Corollary 4.8 gives an o(n) cap whenever ∆/ lg2 n tends to infinity. For smaller ∆, the exact minimum with n remains essential and prevents the asymptotic expression from being misread as an improvement over the trivial cap. For comparison, increasing the palette further gives a sublogarithmic-round endpoint. Corollary 4.9. For fixed λ ≥ 1 and all sufficiently large n, one setting of Algorithm 2 uses O((∆ + 1) lg n/ lg lg n) colors, has frequency cap O(σ + lg n), and runs in O(lg n/ lg lg n) rounds in the CONGEST model and in expected O((m + n) lg n/ lg lg n) sequential time, with probability at least 1 − n−λ . Proof. Set  (∆ + 1) ln n χ=∆+ . ln ln n 

For all sufficiently large n, we have χ ≥ 2∆, so p = 1, θ = ∆/χ, and T = O(lg n/ lg lg n). Moreover, µp,χ =

nT = O(σ), χ−∆

Rprop = O(lg n).

The claim follows from Theorem 4.5 and Eq. (24). For the palette of Corollary 4.9, the ideal frequency is n/χ = Θ(σ lg lg n/ lg n); the cap O(σ +lg n), stated against σ = n/(∆ + 1) for comparability with Corollaries 4.7 and 4.8, therefore exceeds the ideal frequency of its own palette by a factor Θ(lg n/ lg lg n).

5

Discussion

The two procedures avoid global counting by paying different prices. Sampler_Balance retains a genuine two-sided guarantee but inherits the roughly 2∆ palette threshold of its sampling black box. Slack_Greedy approaches ∆ + 1 colors but controls only the upper tail of the color-class sizes. This one-sidedness is a limitation of our proof rather than an established property of the algorithm: by Remark 4.6, every color class has the same expectation, so what is missing is a concentration 15

argument below the mean, not balance in expectation. Whether Slack_Greedy, or a mild variant of it, is in fact near-equitable in the two-sided sense — say, in the load regime σχ = Ω((λ + 1) lg n) in which two-sided guarantees are informative at all — is an open question. The near-exact palette of Corollary 4.8 is most useful in the high-degree regime. For low-degree graphs, the deterministic minimum with n is the meaningful part of the bound. Obtaining a diameter-independent two-sided guarantee with a palette close to ∆ + 1, or obtaining a nontrivial upper cap for all degree regimes, remains open. Another open question, discussed in Remark 4.4, is whether the Θ(lg n) gap between the deterministic proposal budget µp,χ and the expected proposal load O(n/(χ − ∆)) can be closed, which would sharpen the caps of Corollaries 4.7 and 4.8 by a lg n factor. Another natural direction is to replace uniform proper-coloring sampling by a more direct process whose stationary distribution penalizes overloaded colors. Such a process might trade some of the current palette slack for stronger balance, but its local implementation and mixing time would require additional ideas.

References [1] C. Carlson, D. Frishberg, and E. Vigoda. Improved distributed algorithms for random colorings. In Proceedings of OPODIS 2023, volume 286 of LIPIcs, article 13, 2023. [2] K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász Local Lemma and graph coloring. In Proceedings of PODC 2014, pages 134–143, 2014. [3] D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. [4] B. Doerr. Probabilistic tools for the analysis of randomized optimization heuristics. In B. Doerr and F. Neumann, editors, Theory of Evolutionary Computation, pages 1–87. Springer, 2020. [5] W. Feng, T. P. Hayes, and Y. Yin. Distributed symmetry breaking in sampling (optimal distributed randomly coloring with fewer colors). CoRR, abs/1802.06953, 2018. https://arxiv. org/abs/1802.06953. [6] M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lovász Local Lemma, and the complexity hierarchy. In Proceedings of DISC 2017, volume 91 of LIPIcs, pages 18:1–18:16, 2017. [7] M. Fischer and M. Ghaffari. A simple parallel and distributed sampling technique: Local Glauber dynamics. In Proceedings of DISC 2018, volume 121 of LIPIcs, pages 26:1–26:11, 2018. [8] D. A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975. [9] A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. In Combinatorial Theory and Its Applications, II, pages 601–623. North-Holland, 1970. [10] M. M. Halldórsson, F. Kuhn, Y. Maus, and T. Tonoyan. Efficient randomized distributed coloring in CONGEST. In Proceedings of STOC 2021, pages 1180–1193, 2021.

16

[11] D. G. Harris, J. Schneider, and H.-H. Su. Distributed (∆ + 1)-coloring in sublogarithmic rounds. In Proceedings of STOC 2016, pages 465–478, 2016. [12] Ö. Johansson. Simple distributed ∆ + 1-coloring of graphs. Information Processing Letters, 70(5):229–232, 1999. [13] H. A. Kierstead, A. V. Kostochka, M. Mydlarz, and E. Szemerédi. A fast algorithm for equitable coloring. Combinatorica, 30(2):217–224, 2010. [14] H. Lu, M. Halappanavar, D. Chavarría-Miranda, A. Gebremedhin, A. R. Panyala, and A. Kalyanaraman. Algorithms for balanced graph colorings with applications in parallel computing. IEEE Transactions on Parallel and Distributed Systems, 28(5):1240–1256, 2017. [15] W. Meyer. Equitable coloring. American Mathematical Monthly, 80(8):920–922, 1973. [16] A. Nir and D. Peleg. Distributed algorithms for near-equitable coloring. Manuscript submitted for publication, April 2026. [17] A. Nir and D. Peleg. Distributed Near-Equitable Coloring in the LOCAL Model. Manuscript, June 2026. [18] D. Paulin. The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems. Electronic Journal of Probability, 19(68):1–34, 2014.

17

Related documents

• Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs#975083
• Scalable Multi-Controller Coordination in Periplus via Border-Switch Forwarding Graphs#394366
• Trinqet: Private Triangle and Quadrangle Counting over Distributed Graphs#1084663
• An RM-ODP method to model PBL digital twins for supporting closed-loop supervision.#923583
• General Leader-Follower Linear-Quadratic Stochastic Graphon Games with Indefinite Control Weights#1050370