Distributed Algorithms for Near-Equitable Coloring

Distributed Algorithms for Near-Equitable Coloring Amit Nir∗

David Peleg∗

August 5, 2026

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

Abstract For an n-vertex graph of maximum degree ∆ and diameter D, an equitable (∆ + 1)-coloring is a vertex coloring where the frequency of each color (namely, the number of vertices it colors) are all equal to σ = n/(∆+1) (up to rounding) . The Hajnal-Szemerédi Theorem guarantees the existence of such a coloring for every graph, and an O(n2 ∆) time sequential algorithm is known for computing such a coloring. Here, we study near-equitable graph coloring in distributed networks. The main question of interest is how close one can remain to the desired palette size of ∆ + 1 while computing, in few distributed rounds, a coloring whose frequencies are close to σ. It appears that these two conflicting parameters exhibit a tradeoff, which we attempt to explore. We present a suite of fast randomized distributed algorithms representing varying points on this tradeoff, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique (CC) models.

1

Introduction

1.1

Background and motivation

Distributed graph coloring is a fundamental tool for decentralized coordination of parallel activities, with a variety of applications. As each color class forms an independent set of vertices in the graph, the coloring partitions the graph into sets of mutually nonadjacent processors or resources. This can be used for symmetry breaking, conflict-free resource allocation, maximizing parallel processing (while preventing race conditions or deadlocks between concurrently operating vertices), and decentralized scheduling. In scheduling applications, the conflict relation between jobs can be represented by a graph: vertices are jobs, and edges connect jobs that cannot be executed in the same time slot. A proper coloring then gives a feasible schedule, with each color corresponding to one slot and each color class to a set of mutually compatible jobs. This graph-coloring viewpoint is classical in timetabling and examination scheduling [11, 4], and also appears in processor scheduling with mutual exclusion constraints [1]. For certain applications, it may be desirable to use an equitable coloring, namely, a coloring with equal-size (up to ±1) color classes. For example, in scheduling applications as above, a lower bound on the size of a color class prevents underused slots, while an upper bound prevents overloaded ones; in bounded coloring and mutual-exclusion scheduling, this upper capacity is imposed explicitly. Similarly, in parallel graph computations, skewed color classes lead to load imbalance and inefficient ∗

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

1

resource utilization. Imposing a two-sided requirement is also common in load-balanced uses of coloring. The celebrated Hajnal-Szemerédi Theorem [5] guarantees the existence of an equitable coloring with ∆ + 1 colors, where ∆ is the maximum vertex degree. Currently, the fastest constructive algorithm for generating such a coloring is that of Kierstead et al. [8], which finds an equitable χ-coloring in O(χn2 ) time when applied with parameter χ; for ∆ + 1-coloring, this gives O(∆n2 ) sequential time. This algorithm can be transformed in the standard manner1 into a distributed algorithm in the CONGEST or Congested Clique (hereafter, CC) models (cf. [10, 9]). Note that in contrast to coloring, which is essentially a local property, equitability is a global property in nature, which makes it apparently difficult to achieve by purely local algorithms with high probability2 . The following theorem serves as a baseline for our later comparisons. Throughout, we denote sequential time complexity by T seq , time complexity in the CONGEST model by T cngst , and time complexity in the Congested Clique (CC) model by T cc . Theorem 1.1. (Baseline: Equitable coloring) Algorithm EquiColor of Kierstead et al. [8] computes a valid equitable coloring, with palette size χ = ∆ + 1 and frequency thresholds [⌊σ⌋, ⌈σ⌉], where σ = n/(∆ + 1). Its running times2 are T seq (EquiColor) = O(∆n2 ), T cngst (EquiColor) = O(m) and T cc (EquiColor) = O(∆). As faster methods for achieving precise equity might be difficult, we introduce the more relaxed notion of near-equitable coloring, and study algorithms for achieving near-equity, either by relaxing the constraint on the palette size and allowing slightly more than ∆ + 1 colors or by allowing some slack in the equitability requirement (or both). For clarity, we first describe our algorithms in an abstract high-level code, and defer the discussion on their implementation in the sequential setting and in the CONGEST and Congested Clique (CC) distributed models, and the corresponding time analysis, to a later stage (Section 9). Formally, we consider a coloring function ϕ : V 7→ P, assigning each vertex v ∈ V a color from the palette P such that no two neighbors share the same color. The palette size is the number of colors used, denoted χ = |P|. Hereafter, whenever using a partial palette marked Ps (for some descriptor s), we will freely use the notation χs for its size |Ps |, without explicitly defining it. The color class V (i) = {v | ϕ(v) = i} of color i is the set of vertices colored by i, and the frequency of i is the number of vertices colored by i, f(i) = |V (i)|. For a set S of colors, the total P frequency of S, denoted f(S) = i∈S f(i), is the total number of vertices assigned to those colors. n Throughout, we use σ = ∆+1 to denote the “idea” size of a color class. In an equitable coloring, each color class should be of size ⌊σ⌋ or ⌈σ⌉. A near-equitable coloring allows some flexibility: given a predefined frequency range [fmin , fmax ], where fmin and fmax are the (integral3 ) frequency threshold parameters4 , the frequency of each color c must satisfy f(c) ∈ [fmin , fmax ]. (For a strict equitable coloring, the frequency range is [⌊σ⌋, ⌈σ⌉].) 1

We omit a description of these distributed implementations. In this paper we do not consider bounds that hold in expectation. 3 Hereafter, whenever we write [a, b] for non-integral a, b, the intended interval is [⌊a⌋, ⌈b⌉]. 4 Different algorithms in this paper utilize different fmin and fmax values. 2

2

Algorithm Baseline 1: Distributed Coloring

Guarantee Palette: ∆ + 1 Freq: [0, n]

Baseline 2: EquiColor

Palette: ∆ + 1 Freq: [⌊σ⌋, ⌈σ⌉]

Near-Balanced Coloring, NBC

Palette: [ ∆+1 , ∆+1 ] 2ϵ ϵ Freq: [ϵσ, 2ϵσ]

Example with ϵ = 1/3

, 3(∆ + 1)] Palette: [ 3(∆+1) 2 Freq: [σ/3, 2σ/3]

Iter. Near-Bal. Palette: [∆ + 1, 2(∆ + 1)] Coloring, Iter NBC Freq: [σ/2, σ] Palette-Freq. Tradeoff

Palette: (1 + 1/k)(∆ + 1) Freq: [σ/3, 2kσ]

P-F TradeSMALL

Palette-Freq. Tradeoff P-F Trade Palette-Time Tradeoff

Palette: (1 + 1/k)(∆ + 1) Freq: [σ/2, 2kσ] Palette: (1 + 1/k)(∆ + 1) Freq: [σ/3, 2σ]

P-T TradeSMALL

Palette-Time Tradeoff P-T Trade Capped Coloring, Open Recolor

Palette: (1 + 1/k)(∆ + 1) Freq: [σ/2, 2σ]

Example with α=1

Palette: (1.5 + ϵ)(∆ + 1) Freq: [σ/2, σ]

Optimal palette, LogCap Compact

Palette: ∆ + 1 Freq: [σ/2, 2σ + lg(∆ + 1) ·(1 + ε)σ] for σ = Ω(lg n)

Palette: (1 + ρ(α)) · (∆ + 1) + 1 for ρ(α) = (1 + 2ϵ)/(2α) Freq: [σ/2, ασ] (α ≥ 1)

Running time Seq: O(m), det. CONGEST: O(lg5 lg n), rand., w.h.p. CC: O(1), det. Seq: O(n2 ∆), det. CONGEST: O(m), det. CC: O(∆), det. Seq: O(m), det. CONGEST: O(D + ∆ + lg5 lg n), rand., w.h.p. CC: O(1), det. Seq: O(m), det. CONGEST: O(D + ∆ + lg5 lg n), rand., w.h.p. CC: O(1), det. Seq: O(m lg ∆), det. CONGEST: O(lg ∆ · (D + ∆ + lg5 lg n)), rand., w.h.p. CC: O(lg ∆), det. Seq: O(m), det. CONGEST: O(D + ∆ + lg5 lg n), rand., w.h.p. CC: O(1), det. Seq: O(m lg ∆), det. CONGEST: O(lg ∆ · (D + ∆ + lg5 lg n)), rand., w.h.p. CC: O(lg ∆), det. Seq: O(mk), det. CONGEST: O(k · (D + ∆ + lg5 lg n)), rand., w.h.p. CC: O(k), det. Seq: O(m(k + lg ∆)), det. CONGEST: O((lg ∆ + k) · (D + ∆ + lg5 lg n)), rand., w.h.p. CC: O(k + lg ∆), det. Seq: O(m lg n) CONGEST: O((D + ∆) lg n + lg ∆ · lg5 lg n) CC: O(lg n) All: rand., w.h.p. Seq: O(m lg n) CONGEST: O((D + ∆) lg n + lg ∆ · lg5 lg n) CC: O(lg n) All: rand., w.h.p. Seq: O(m lg n lg ∆) CONGEST: O((D + ∆) lg n lg ∆) CC: O(lg n lg ∆) All: rand., w.h.p.

Src cf. [7] [2, 3] [8]

Sec. 3

Sec. 4

Sec. 5

Sec. 6

Sec. 7

Sec. 8

Table 1: Comparison of near equitable coloring algorithms and their running times in the CC, CONGEST, and sequential models (ceilings/floors omitted for readability).

1.2

Our contributions

The central question studied in this work concerns the potential tradeoffs between the palette size χ and the frequency range [fmin , fmax ] that can be achieved by randomized distributed algorithms. Our main results, summarized in Table 1, sketch the trade-offs available for distributed equitable coloring, ranging from time-costly perfectly equitable solutions to time-efficient approximations. Hereafter, for a given graph G, we denote by n, m, ∆, D its number of vertices, number of edges, maximum degree and diameter, respectively.

3

1.2.1

Basic tools

The algorithms described later on are assembled from a small toolbox consisting of a number of primitives and procedures, whose implementation depends on the computational model. These are the following: Color accounting (CA). This primitive computes aggregate information per color and disseminates the result. Its uses include, for example, computing the frequencies of colors, sorting colors by frequencies, identifying colors whose frequency is too small or too large, informing vertices that need to recolor themselves (and by which color classes), and maintaining various global counters on the colors. Quota assignment (QA). This primitive receives, for some color i, a set Ci of vertices that request to be colored by i and a quota bi , and admits exactly min{|Ci |, bi } candidates. The other candidates are informed that their request was denied. Procedure Color All(G, χ): This procedure is used by our algorithms for the basic initialization of the coloring. It invokes a standard list-coloring procedure LC with target set V and color lists L(v) = {1, . . . , χ} for every vertex. The resulting coloring ϕ makes no guarantees on color frequencies. Procedure Recolor(Vtarget , Ptarget ): This procedure is used for modifying an existing coloring. It is typically invoked after some colors were disqualified (say, due to having too small frequencies), and the corresponding vertices were uncolored. These vertices form the set Vtarget that needs to be recolored. Ptarget is the set of colors to be used for these vertices. For ease of comparison, the main result statements below include the sequential, CONGEST and Congested Clique running times. The model-dependent implementation details leading to these time bounds are deferred to Section 9. 1.2.2

Near-Balanced Coloring (NBC)

In Section 3, we present a basic O(1) CC-time Near-Balanced Coloring algorithm (NBC) that produces a coloring with frequency range [εσ, 2εσ] for ε ≤ 1/3. The algorithm employs a basic one-shot split & recolor paradigm: It generates an initial valid coloring, applies Procedure Split to eliminate large-frequency colors, then applies Procedure Recolor to eliminate small-frequency colors, and finally invokes Procedure Split again to get rid of any newly generated large-frequency colors. The simplicity of this algorithm hinges on two facts. First, the considered frequency ranges are doubling, i.e., fmax ≥ 2fmin , making it simpler to use Procedure Split (Section 2.3). Second, its upper frequency threshold is smaller than σ, which necessitates using more than ∆ + 1 colors and makes Procedure Recolor easier to apply. We get the following result. Theorem 1.2. For every ε ≤ 1/3, Algorithm NBC computes a valid coloring with palette size χ ∈ [(∆ + 1)/2ε, (∆ + 1)/ε] and frequency thresholds [εσ, 2εσ]. For fixed ε, its running times are T seq (NBC) = O(m) and T cc (NBC) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (NBC) = O(D + ∆ + lg5 lg n) with high probability.

4

1.2.3

Iterative Near-Balanced Coloring (Iter NBC)

We next turn to examining frequency ranges with slightly larger (yet still doubling) thresholds, particularly fmin = ⌊σ/2⌋ and fmax = ⌈σ⌉. For this purpose, we make use of an iterative split & recolor paradigm, where the splitting and recoloring steps are repeated a number of times. The range is still doubling, so splitting remains safe, but it is closer to the ideal frequency σ and therefore leaves less slack in the number of available target colors. Specifically, Section 4 introduces the Iterative Near-Balanced Coloring (Iter NBC) algorithm, which applies procedures Recolor and Split repeatedly for O(lg ∆) iterations. The algorithm uses the same initial coloring algorithm Color All. Then, each iteration consists of invoking Procedure Split with threshold fmax = σ, so no current color is too large, followed by Procedure Recolor, which uses the ∆ + 1 most frequent colors as a target palette, and recolors all remaining colors. Each individual iteration suffers from the same basic difficulty as before: After each recoloring step, the next split repairs the upper bound; after each split, the next recoloring step again eliminates the less frequent colors. Hence again, the concern is that the introduction of new colors in the splitting phases might undo the progress made by the recoloring phases. The analysis shows that this does not happen. In each iteration, the split step creates no new small colors, and the subsequent recoloring step eliminates more than half of the small colors present after the split. Thus, the number of small colors decreases geometrically across the iterations. At the cost of increasing the CC runtime to O(lg ∆), this algorithm achieves a frequency range of [σ/2, σ] with palette size χ ≤ 2(∆ + 1). We get the following result. Theorem 1.3. Algorithm Iter NBC computes a valid coloring with palette size χ ∈ [∆ + 1, 2(∆ + 1)] and frequency thresholds [σ/2, σ]. Its running times are T seq (Iter NBC) = O(m lg ∆) and T cc (Iter NBC) = O(lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (Iter NBC) = O(lg ∆ · (D + ∆ + lg5 lg n)) with high probability. 1.2.4

Palette - Frequencies Tradeoff (P-F Trade)

Next, Section 5 presents a generalized algorithm that, for any parameter k ≥ 1, achieves a palette size of (1 + 1/k)(∆ + 1) with frequency range [σ/2, 2kσ]. To achieve this, we revisit the simpler one-shot split & recolor paradigm, but introduce two modifications. First, we “bootstrap” the process by using Algorithm Iter NBC of Section 4 to generate the initial coloring. Secondly, we use a much larger upper frequency threshold of fmax = 2kσ for the final splitting step, thus reducing the need for splitting and allowing us to end up with fewer colors. In the recoloring stage, the algorithm uses the ∆+1 most frequent colors to recolor all remaining vertices. This may create large color classes, so the final step applies Split with the relaxed upper threshold 2kσ. Thus, the parameter k controls the trade-off: a larger k allows larger frequencies and yields a palette closer to ∆ + 1. Theorem 1.4. For every integer parameter k ≥ 1, Algorithm P-F Trade computes a valid coloring with palette size χ ≤ (1 + 1/k)(∆ + 1) and frequency thresholds [σ/2, 2kσ]. Its running times are T seq (P-F Trade) = O(m lg ∆) and T cc (P-F Trade) = O(lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (P-F Trade) = O(lg ∆ · (D + ∆ + lg5 lg n)) with high probability.

5

Theorem 1.5. For every integer parameter k ≥ 1, Algorithm P-F TradeSMALL computes a valid coloring with palette size χ ≤ (1 + 1/k)(∆ + 1) and frequency thresholds [σ/3, 2kσ]. Its running times are T seq (P-F TradeSMALL ) = O(m) and T cc (P-F TradeSMALL ) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (P-F TradeSMALL ) = O(D + ∆ + lg5 lg n) with high probability. 1.2.5

Palette - Time Tradeoff (P-T Trade)

In Section 6, we further optimize the convergence rate, achieving a palette of (1 + 1/k)(∆ + 1) with tighter frequency range [σ/2, 2σ], but at the cost of increasing the CC time complexity to O(k + lg ∆). So, the resulting algorithm, P-T Trade, yields a trade-off complementary to that of Algorithm P-F Trade of Section 5. The algorithm is based on the iterative split & recolor paradigm, using Algorithm Iter NBC for the initial coloring and continuing the iterations until the number of colors drops below the desired bound. Instead of allowing the upper frequency threshold to grow with k, the algorithm keeps the tighter frequency range [σ/2, 2σ]. The price is increased time: it repeatedly compacts the palette to the largest ∆ + 1 colors and then splits colors above 2σ, so the excess palette size decreases by about (∆ + 1)/k in each iteration. Theorem 1.6. For every integer parameter k ≥ 1, P-T Trade (Algorithm 5) computes a valid coloring with palette size χ ≤ (1 + 1/k)(∆ + 1) and frequency thresholds [σ/2, 2σ]. Its running times are T seq (P-T Trade) = O(m(k + lg ∆)) and T cc (P-T Trade) = O(k + lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (P-T Trade) = O((lg ∆ + k) · (D + ∆ + lg5 lg n)) with high probability. Theorem 1.7. For every integer parameter k ≥ 1, Algorithm P-T TradeSMALL computes a valid coloring with palette size χ ≤ (1 + 1/k)(∆ + 1) and frequency thresholds [σ/3, 2σ]. Its running times are T seq (P-T TradeSMALL ) = O(mk) and T cc (P-T TradeSMALL ) = O(k). In the CONGEST model, the coloring is obtained in time T cngst (P-T TradeSMALL ) = O(k ·(D +∆+lg5 lg n)) with high probability. 1.2.6

Capped / open Reoloring (Open Recolor)

Section 7 presents Algorithm Open Recolor, which refines the iterative approach, reducing the palette size to (1.5 + ϵ)(∆ + 1) while maintaining the O(lg n) CC runtime and the frequency range [σ/2, σ]. More generally, the algorithm is parameterized by an upper-frequency factor α ≥ 1 (setting fmax = ασ) and an integer excess ℓ over the optimal palette size ∆ + 1. We write β = 1 + ℓ/(∆ + 1), so the target palette has χtarget = β(∆ + 1) = ∆ + 1 + ℓ colors, and the resulting frequency range is [σ/2, ⌈ασ⌉]. The main idea behind Algorithm Open Recolor is the following. Recall that Algorithm Iter NBC (Section 4) is based on the iterative split & recolor paradigm, alternating between recoloring phases, which reduce the number of colors at the cost of increasing the frequencies of the remaining colors, and splitting phases, which increase the number of colors. In contrast, the new approach aims to prevent the need for splitting entirely, thus reducing the number of phases. To achieve that, we no longer treat all colors with frequency at most fmax as valid targets in the recoloring stage. Rather, we forbid the use of a color c if its frequency f(c) is so close to fmax that there’s a risk that it might exceed fmax if c is used in the recoloring stage. Following this idea, the key new ingredient is to recolor uncolored vertices using the target palette while enforcing the upper threshold deterministically. To this end, we use an open-cap 6

parameter φ < 1 to determine which colors are still available during the recoloring phase, and define an intermediate capping threshold fcap = ⌊φασ⌋ in-between fmin and fmax . A color i is now considered open only while its frequency satisfies f(i) ≤ fcap . Colors with frequency above fcap are declared closed. Only open colors may be used for coloring vertices at the recoloring stages, and moreover, each open color can be used only up to its remaining capacity, fmax − fcap . The parameters α, ℓ, β, φ are chosen to satisfy β =1+

ℓ for 1 ≤ ℓ ≤ ∆, ∆+1

α ≥ 1,

1 < φ < 1, 2

2φα ·

ℓ > 1. ∆+1

Under these constraints, we have the following result. Theorem 1.8. For fixed constant parameters satisfying the conditions above, Algorithm Open Recolor computes, with high probability, a valid coloring with palette size χ ≤ β(∆+1) and frequency thresholds [σ/2, ⌈ασ⌉]. Its running times are T seq (Open Recolor) = O(m lg n), T cngst (Open Recolor) = O((D + ∆) lg n + lg ∆ · lg5 lg n) and T cc (Open Recolor) = O(lg n). 1.2.7

Optimal ∆ + 1 palette (LogCap Compact)

Section 8 pushes the palette size down to ∆ + 1 by applying the capped recoloring idea gradually until χ = ∆ + 2, and then with one last Recolor gets to χ = ∆ + 1. In each phase, the algorithm removes roughly half of the current excess colors and recolors their vertices into the remaining palette, while allowing every “surviving” color (that was not eliminated during the color reduction process) to gain only O(σ) new vertices. Since the number of phases is O(lg ∆), the price for the ∆ + 1 palette is a larger upper frequency threshold of O(lg ∆ · σ). The external parameters of Algorithm LogCap Compact are the slack parameter 0 < ε ≤ 1 and the failure-probability exponent c ≥ 1. The parameter ε controls the amount of extra capacity available in each phase: a color i that is still in P maintains a counter fadd (i) for the number of new vertices assigned to it in the current phase, may receive at most fph max = ⌈(1 + ε)σ⌉ new vertices, and is open only while fadd (i) ≤ fcap , where fcap = ⌊(1 + ε/2)σ⌋. Thus the gap fph max − fcap = Ω(εσ) serves as a safety buffer (to be used for the concentration arguments in the analysis). The exponent c sets the final success probability 1 − n−c . Finally, if a phase has target palette size ∆ + 1 + s, then s denotes the current excess over ∆ + 1; the phase removes (at most s) low-frequency colors from this excess and recolors their vertices using the surviving palette. The analysis establishes that the excess decreases geometrically, so there are O(lg ∆) phases, which gives the final upper frequency threshold σ + ⌈lg(∆ + 1)⌉fph max . The parameters ε, c are chosen to satisfy 0 < ε ≤ 1,

c ≥ 1,

σ ≥ max{6/ε, (100/ε)(c + 6) lg n}.

Theorem 1.9. For fixed constant parameters satisfying the conditions above, Algorithm LogCap Compact computes, with probability at least 1 − n−c , a valid coloring with palette size χ = ∆ + 1 and frequency thresholds [σ/2, 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉]. Its parameter-dependent running times are T seq (LogCap Compact) = O(m lg n lg ∆), T cngst (LogCap Compact) = O((D + ∆) lg n lg ∆) and T cc (LogCap Compact) = O(lg n lg ∆).

7

2

Basic tools

2.1

Communication and coordination primitives

The remaining primitive interfaces are used to coordinate choices indexed by colors. They do not by themselves recolor vertices; instead, they provide the global accounting and admission steps used by the procedures and algorithms. Color accounting (CA). The color-accounting primitive computes aggregate information per color and disseminates the result. Its uses include, for example, computing the frequency f(i) of a color i, sorting the colors by non-increasing order of frequency, identifying the palette Premove of colors whose frequency is too small and therefore should be removed, informing all vertices currently using colors from Premove that they need to recolor themselves, and announcing to all those vertices the target palette Ptarget to be used in the recoloring process, testing whether a target set is empty, and maintaining various global counters on the colors. Quota assignment (QA). The quota-assignment primitive receives, for each color i, a candidate set Ci of vertices that request to be colored by i and a quota bi , and admits exactly min{|Ci |, bi } candidates. The other candidates are informed that their request was denied. More specifically, when an algorithm invoking QA uses random ranks, the primitive QA admits the highest-ranked feasible candidates. This interface is used both for capacity-aware recoloring (for example Algorithm 6 (Open Recolor) of section 7) and for assigning vertices of a split color to its descendant colors. Lemma 2.1. Assume that the primitives QA or CA are invoked for handling O(∆) color records. Then they have the following implementation costs: T seq (CA) = T seq (QA) = O(m), T cngst (CA) = T cngst (QA) = O(D + ∆) and T cc (CA) = T cc (QA) = O(1).

2.2

List Coloring, Color All and Recolor

The first set of key primitives we use concerns coloring. Underlying these operations is the list coloring operation. List Coloring (LC). Given a target set V ′ ⊆ V and, for each v ∈ V ′ , a list L(v) of admissible colors, LC returns a valid coloring of V ′ from these lists, consistent with the colors already assigned to V \ V ′ . We do not develop any new algorithms for LC, but rather use existing LC algorithms for our needs. Specifically, we use this primitive to implement two procedures, named Color All and Recolor, each involving a single application of LC, without using any additional communication primitives. Procedure Color All(G, χ): This procedure is used by our algorithms for the basic initialization of the coloring. It invokes LC with target set V and color lists L(v) = {1, . . . , χ} for every vertex. The resulting coloring ϕ makes no guarantees on color frequencies. Lemma 2.2. Given a palette P of size χ ≥ ∆ + 1, Procedure Color All(G, χ) produces a valid coloring ϕ : V → P using at most χ colors. At the interface level, this is one call to LC. Its running times are T seq (Color All) = O(m) and T cc (Color All) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (Color All) = O(lg5 lg n) with high probability.

8

Throughout, the implementation details in the three settings and the analysis of the time bounds stated in our lemmas are deferred to Section 9. Procedure Recolor(Vtarget , Ptarget ): This procedure is used for modifying an existing coloring. It is typically invoked after some colors were disqualified (say, due to having too small frequencies), and the corresponding vertices were uncolored. These vertices form the set Vtarget that needs to be recolored. Ptarget is the set of colors to be used for these vertices. The procedure extends the current partial coloring by invoking LC on Vtarget , where each vertex deletes from Ptarget the colors already used by its colored neighbors. Lemma 2.3. Let ϕ be a valid partial coloring of G with a set Vtarget of uncolored vertices, and let Ptarget be a target palette of size χtarget = |Ptarget | ≥ ∆ + 1. Then Recolor(Vtarget , Ptarget ) extends the partial coloring ϕ to a valid coloring of G in which every vertex of Vtarget receives a color from Ptarget . Letting each vertex learn Ptarget requires a CA operation. Then, the procedure consists of one call to LC. Its running times are T seq (Recolor) = O(m) and T cc (Recolor) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (Recolor) = O(D + ∆ + lg5 lg n) with high probability. Remark 2.4. Throughout the paper, whenever a color i is dissolved and V (i) becomes empty, we implicitly assume that i is erased from our palette (i.e., we do not write this change explicitly in the code). Remark 2.5. The schematic modular decomposition of our algorithms into basic primitives for the sake of time complexity analysis may be somewhat artificial, especially for the sequential implementation, where color accounting and quota assignments can be performed directly. We use this scheme mainly for simplifying the time analysis of the distributed implementations of our algorithms. We discuss this in more detail in Section 9.

2.3

Safe splitting: reducing large color classes

We now present Procedure Split, used for reducing the color frequencies of a given coloring ϕ below a specified upper threshold fmax , by splitting large color classes. This is done by first identifying colors whose frequency exceeds the threshold (using the primitive CA to count the frequency of each color), and then creating, for each such color i, the necessary number of new descendant colors of prescribed (smaller) sizes replacing it, and assigning the vertices of V (i) to these descendant colors (using the primitive QA). Lemma 2.6. Consider an execution of Procedure Split(ϕ, fmax ) on a valid coloring ϕ of a graph G and a frequency threshold fmax ≥ 1. (a) Split returns a valid coloring. (b) If a color i is split during the execution, then any created color inew has frequency f(inew ) ≥ ⌈fmax /2⌉. (c) If the input coloring satisfies f(i) ≥ fmin for every color i and fmin ≤ ⌊fmax /2⌋, then every output color satisfies f(i) ∈ [fmin , fmax ]. (d) The running times of Procedure Split are T seq (Split) = O(m), T cngst (Split) = O(D+∆), T cc (Split) = O(1). Proof. Each color class V (i) is an independent set, so its partition into disjoint sets preserves the independence property. Thus, the resulting coloring is valid, establishing (a). 9

Algorithm 1: Split(ϕ, fmax ) 1 Input: A current coloring ϕ : V → P, frequency threshold fmax ≥ 2. 2 Output: A refined coloring ϕ′ with upper frequency threshold fmax . 3 ϕ′ ← ϕ 4 Plarge ← {i ∈ P | f(i) > fmax } 5 for each color i ∈ Plarge (in parallel) do 6 7 8 9 10 11 12

Let f(i) = k · fmax + t for 0 ≤ t < fmax If t ≥ 1 then split V (i) into r = k + 1 disjoint sets: V1 , . . . , Vk−1 of size fmax , Vk of size ⌊(fmax + t)/2⌋ and Vk+1 of size ⌈(fmax + t)/2⌉. Else (t = 0, k ≥ 2) split V (i) into r = k disjoint sets: V1 , . . . , Vk of size fmax . Generate r new unique colors i1 , . . . , ir . for every j ∈ {1, . . . , r} do: set ϕ′ (v) ← ij for every v ∈ Vij . P ← (P \ {i}) ∪ {i1 , . . . , ir }

13 return ϕ′

To prove part (b), consider a color i selected for splitting. By the loop condition, f(i) > fmax , and recalling that fmax is integral by convention and f(i) is integral by definition, we have f(i) ≥ fmax + 1. The algorithm splits the color i into new colors, where each new color inew has frequency   fmax f(inew ) ≥ min{fmax , ⌊(fmax + 1)/2⌋} ≥ , (1) 2 where the final equality follows since fmax is integral. Claim (c) follows because unsplit colors preserve the input lower bound, and created colors inew have frequency f(inew ) ≥ ⌈fmax /2⌉ ≥ fmin , and the procedure terminates only after all frequencies are at most fmax . The runtime bounds in part (d) follow from part (c) and Lemma 2.1: Split performs one CA step to identify the colors to split and compute the descendant quotas, and one QA step to assign vertices to the descendant colors; the model-specific implementations of these primitives are deferred to Section 9.

3

Small Frequency Range Near Balanced Coloring

In this section, we present and analyze a distributed algorithm that achieves a near-equitable coloring. This algorithm employs a basic one-shot split & recolor paradigm: It generates an initial valid coloring, applies Procedure Split to eliminate large-frequency colors, then applies Procedure Recolor to eliminate small-frequency colors, and finally invokes Procedure Split again to get rid of any newly generated large-frequency colors. While several of our later results aim at using at most 2(∆ + 1) colors with lower frequency threshold σ/2, this section aims at generating a coloring with many colors and a lower frequency threshold of εσ for small ε. We classify colors into three categories based on their frequency f(i) relative to the algorithm’s specific frequency thresholds fmin and fmax .

10

• Small: The color i is underpopulated, with f(i) < fmin . Each small color i is a candidate for dissolution (by recoloring the vertices in V (i)). • Good: The color i is balanced, with f(i) ∈ [fmin , fmax ]. This is the desired state. • Large: The color i is overpopulated, with f(i) > fmax . These colors must be split to reduce their frequency. We denote the corresponding color palettes by: Psmall = {i ∈ P | f(i) < fmin },

(2)

Pgood = {i ∈ P | f(i) ∈ [fmin , fmax ]}, Plarge = {i ∈ P | f(i) > fmax }. Let us start with describing the main idea for the first near-equitable coloring algorithm. Fix a constant ε = 1/M for an integer M ≥ 3, and set the target frequency range to [fmin , fmax ] = [εσ, 2εσ]. Since the upper threshold is below σ when ε ≤ 1/3, a coloring in this range must use more than ∆ + 1 colors. The advantage is that this additional palette slack makes it possible to apply the one-shot split & recolor paradigm directly. The algorithm first runs Color All, which gives a valid coloring but does not bound the color frequencies. It then applies Split to every color whose frequency is larger than fmax . After this step, no color is large: each color is either good, or is small and should be dissolved. The next step is to recolor all vertices that currently belong to small colors, using only the good colors as the target palette. A natural concern is that after removing the small colors, too few colors might remain available for applying Recolor. This is exactly where the choice ε ≤ 1/3 is used: since every good color has frequency at most 2εσ ≤ 2σ/3, a volume argument shows that there are at least ∆ + 1 good colors (Lemma 3.2), and therefore the target palette is large enough for the recoloring step. This recoloring may increase the frequencies of the good colors and may therefore create new large colors. The final call to Split repairs this by enforcing the upper threshold fmax again. Since the range is doubling, namely fmax ≥ 2fmin , splitting a color whose frequency exceeds fmax creates new colors of frequency at least fmax /2 = fmin . Hence the final split restores the upper bound without creating new small colors. Consequently, the algorithm returns a valid coloring whose frequency range is [εσ, 2εσ] and whose palette size is in the range [(∆ + 1)/(2ε), (∆ + 1)/ε]. The formal description of Algorithm NBC is given in Algorithm 2 (NBC).

Correctness proof and analysis Lemma 3.1. Applying Procedure Split with frequency threshold fmax = 2εσ guarantees that any resulting color i′ has frequency f(i′ ) ≥ fmin . Consequently, splitting a large frequency color (in Plarge ) never creates a small-frequency color (in Psmall ). Proof. Applying Lemma 2.6 with fmax = ⌈2εσ⌉, a split color i with f(i) > fmax results in new colors i′ satisfying f(i′ ) ≥ fmax /2 ≥ εσ ≥ ⌊εσ⌋ = fmin , so i′ ∈ Psmall . Lemma 3.2. If the initial coloring uses at most ∆ + 1 colors, then |Pgood | ≥ ∆ + 1. 11

Algorithm 2: NBC(G, ε): Distributed Near-Balanced Coloring 1 Input: Graph G = (V, E) with maximum degree ∆ and size n = |V |, parameter ε. 2 Output: A valid coloring ϕ : V → P with frequency range [εσ, 2εσ] 3 fmin ← εσ; fmax ← 2εσ 4 ϕ ← Color All(G, ∆ + 1)

▷ frequency threshold parameters ▷ Initialization: Start with a valid coloring 5 ϕ ← Split(ϕ, fmax ) ▷ Reduce all class frequencies to ≤ fmax 6 Psmall ← {i ∈ P | f(i) < fmin }; P ← {i ∈ P | f(i) ∈ [fmin , fmax ]} good S 7 Vsmall ← ▷ Vertices to be recolored i∈Psmall V (i) 8 Recolor(Vsmall , Pgood ) ▷ Recolor Vsmall using palette Pgood 9 ϕ ← Split(ϕ, fmax ) ▷ Recoloring may have caused colors in R to exceed fmax 10 return ϕ

Proof. Let P ◦ = P \ Psmall denote the set of all non-small colors before any splitting occurs. The sum of frequencies in the graph satisfies f(Psmall ) + f(P ◦ ) = n.

(3)

First, we bound f(Psmall ). The maximum frequency of any color i ∈ Psmall satisfies f(i) < εσ. Since the initial valid coloring (obtained by Algorithm Color All) uses at most ∆ + 1 colors, we have |Psmall | ≤ ∆ + 1. Therefore, X εn f(Psmall ) = f(i) < |Psmall | · εσ = |Psmall | · ≤ εn, ∆+1 i∈Psmall

so combined with Eq. (3), f(P ◦ ) = n − f(Psmall ) > (1 − ε)n. The splitting process performed in Step 9 (defined in Lemma 2.6) ensures that any color in P ◦ is either already in Pgood or is split into colors that end up in Pgood . Thus, f(Pgood ) ≥ f(P ◦ ) > (1−ε)n. Finally, we lower bound |Pgood |. Since every color i ∈ Pgood satisfies the upper bound f(i) ≤ 2εn 2εσ = ∆+1 , the minimum number of colors required to account for f(Pgood ) is |Pgood | ≥

f(Pgood ) (1 − ε)n 1−ε > = (∆ + 1) ≥ ∆ + 1, 2εn maxi∈Pgood f(i) 2ε ∆+1

where the last inequality follows from the fact that ε = 1/M ≤ 1/3. Lemma 3.3. Given a graph G and an initial coloring with f(i) ≥ εσ for every color i, Procedure Split returns a refined coloring with frequency range [εσ, 2εσ]. Proof. Let fmin = ⌊εσ⌋ and fmax = ⌈2εσ⌉. Note that fmax ≥ 2fmin . The algorithm proceeds in phases. In each phase, every color i performs the following operations in parallel (as described in Procedure Split (Algorithm 1)): In each round, the nodes compute the current frequency f(i). • If f(i) ≤ fmax , the color satisfies the upper bound. Since the initial coloring assumed in the lemma guarantees f(i) ≥ fmin and no action is taken, the bounds hold. 12

• If f(i) > fmax , color i is split: V (i) is partitioned into two disjoint subsets V (i1 ) and V (i2 ), with frequencies f(i1 ) = ⌊f(i)/2⌋ and f(i2 ) = ⌈f(i)/2⌉. This process repeats until all colors satisfy f(i) ≤ fmax . We proved in 3.1 that splitting a color which violates the upper bound never results in a color that violates the lower bound. Thus, for any resulting new color i′ , f(i′ ) > fmin . This ensures that the lower bound f(i′ ) ≥ εσ is maintained throughout the execution. When the process terminates, all colors satisfy the upper bound f(i) ≤ 2εσ. Thus, the final coloring satisfies f(i) ∈ [εσ, 2εσ] for every i. For the sake of the time analysis of Section 9 we note the following: Fact 3.4. Algorithm NBC makes one call to Color All, two calls to Split, one CA step to classify colors into Psmall and Pgood , and one call to Recolor. Theorem 3.5. For a graph G and a parameter ε ≤ 1/3, Algorithm NBC(G, ε) computes a valid coloring ϕ with palette size χ ∈ [(∆+1)/(2ε), (∆+1)/ε] and frequency range [fmin , fmax ] = [εσ, 2εσ]. Its running times are T seq (NBC) = O(m) and T cc (NBC) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (NBC) = O(D + ∆ + lg5 lg n) with high probability. Proof. The initialization executes Procedure Color All with a palette of size χ = (∆ + 1). and produces a valid coloring ϕinit . The splitting procedure of Step 5, described in Lemma 3.3, is applied to all colors in ϕinit . Any color i with f(i) > fmax is split recursively. At the end of this phase, all colors satisfy f(i) ≤ fmax . Step 6 classifies the colors into two sets, Psmall and Pgood . By Lemma 3.2, since the total frequency is n and f(Psmall ) is bounded (due to the bounded number of initial colors), the number of good colors satisfies |Pgood | ≥ ∆ + 1. Step 7 now dissolves the small colors by applying Procedure Recolor, treating the vertices in Vsmall as uncolored and the set Pgood as the global palette of available colors. We have a valid partial coloring on V \ Vsmall using colors from Pgood . The palette size is |Pgood | ≥ ∆ + 1. By Lemma 2.3, we can extend the coloring to Vsmall using the palette Pgood . After this phase, all vertices are colored with colors from Pgood . The set Psmall is empty. The recoloring in Step 7 may have caused some colors i ∈ Pgood to grow beyond the upper bound fmax (as they absorbed nodes from Psmall ). Step 9 achieves the final balancing by applying Procedure Split on Pgood one final time. By Lemma 3.1, splitting a color with frequency larger than fmax results in new colors strictly above fmin in frequency. Thus, no new Small colors are created. The final coloring ϕ is valid as it is obtained from extending a valid initial coloring and splitting colorP classes (which are independent sets). All colors i ∈ P satisfy f(i) ∈ [fmin , fmax ]. Recall that n = i∈P f(i). Since f(i) ≥ fmin for all i, we have n ≥ χ · fmin , so χ≤

n fmin

=

n

εn = ∆+1

∆+1 . ε

Conversely, since f(i) ≤ fmax for all i, we have n ≤ χ · fmax , so χ≥

n fmax

=

n

2εn = ∆+1

∆+1 . 2ε

Thus, χ ∈ [(∆ + 1)/(2ε), (∆ + 1)/ε]. The runtime bounds follow from Fact 3.4 and are calculated in Section 9. The theorem follows. 13

Corollary 3.6. Taking the maximal value ε = 1/3, we obtain a coloring with frequency range [ σ3 , 2σ 3 ], palette size χ in [1.5(∆ + 1), 3(∆ + 1)].

4

Iterated near-equitable coloring algorithm (Iter NBC)

The previous section applied the one-shot split & recolor paradigm to handle small ranges of the form [εσ, 2εσ], where the upper threshold was below σ. In this section, we aim to reach the higher frequency range [fmin , fmax ] = [σ/2, σ]. For this purpose, one activation of Split and Recolor no longer suffices. Instead, we make use of an iterative split & recolor paradigm, where the splitting and recoloring steps are repeated for O(lg ∆) times. The algorithm uses the same initial coloring algorithm Color All. Then, each iteration consists of invoking Procedure Split with threshold fmax = σ, so no current color is too large, followed by Procedure Recolor, which uses the ∆ + 1 most frequent colors as a target palette, and recolors all remaining colors. The analysis shows that the split steps do not create new small colors, and in each iteration, the recoloring step eliminates more than half of the remaining small colors. Thus, the number of small colors decreases geometrically with the iterations. A final call to Split enforces the upper bound one last time. Thus, the algorithm returns a valid coloring with at most 2(∆ + 1) colors, and every color has frequency in [σ/2, σ]. The formal description of Algorithm Iter NBC is given in Algorithm 3 (Iter NBC). Algorithm 3: Iterative Distributed Near Balanced Coloring Procedure Iter NBC(G) 1 Input: Graph G = (V, E) of size n and Maximum Degree ∆. 2 Output: A valid coloring with χ ≤ 2(∆ + 1) and frequency range [σ/2, σ]. 3 fmin ← σ/2;

fmax ← σ 4 ϕ ← Color All(G, ∆ + 1) ▷ Obtain initial valid ∆ + 1 coloring 5 for t = 1 to O(lg ∆) (sequentially) do 6 ϕ ← Split(ϕ, fmax ) 7 Sort colors in P by nonincreasing order of frequency f(i): i1 , i2 , . . . , iχ . 8 Ptarget ← S {i1 , . . . , i∆+1 } ▷ Top ∆ + 1 most frequent colors 9 Vtarget ← i∈P\Ptarget V (i) 10 Recolor(Vtarget , Ptarget ) ▷ Recolor Vtarget using palette Ptarget 11 ϕ ← Split(ϕ, fmax )

▷ Final Split

12 return ϕ

Correctness proof and analysis n Recall that σ = ∆+1 . We classify colors at any stage of the execution into the three families Psmall , Pgood and Plarge , defined in Eq. (2). The next lemma follows directly from Lemma 2.6 with fmax = σ.

Lemma 4.1. The invocations of Procedure Split (with frequency threshold fmax = σ) to large colors i ∈ Plarge (where f(i) ≥ σ) result in good colors (with frequency in [σ/2, σ]), creating no new small 14

colors. t For each iteration t of the loop, let Psmall be the set of small colors at the beginning of Step 7, t and let Premove be the set P \ Ptarget defined in Steps 7 - 8. t t Lemma 4.2. At least half of the colors in Psmall are in Premove and are eliminated in Step 10. 1 t t t Formally, |Psmall ∩ Premove | ≥ 2 |Psmall |. t t Proof. Let qt = |Psmall ∩ Ptarget | be the number of small colors retained in the target palette in t t iteration t. Let g = |Pgood | and s = |Psmall | be the number of good and small colors after the Split t step of iteration t (recall that Plarge is empty after the split). t Summing the total frequencies, and recalling that f(i) ≤ σ for i ∈ Pgood and f(i) < σ/2 for t i ∈ Psmall , we get t t g · σ + s · σ/2 ≥ f(Pgood ) + f(Psmall ) = n,

hence g + s/2 ≥ n/σ = ∆ + 1.

(4)

Good colors have no lower frequency than small colors. Therefore, if qt > 0, then some small color is t t t |−g = ∆+1−g. . In this case, qt = |Ptarget , and all good colors must also belong to Ptarget in Ptarget t , and we are done. Otherwise, by Eq. (4), If qt = 0 then all small colors belong to Premove t t qt = ∆ + 1 − g ≤ s/2, so |Psmall ∩ Premove | = s − qt ≥ s/2. The lemma follows.

For the sake of the time analysis of Section 9 we note the following: Fact 4.3. Algorithm Iter NBC makes one initial call to Color All, then performs O(lg ∆) iterations, each containing one call to Split, one CA step for sorting and selecting Ptarget , and one call to Recolor. It ends with one additional call to Split. Theorem 4.4. Procedure Iter NBC(G) (Algorithm 3) produces a valid coloring with χ ∈ [(∆ + 1), 2(∆ + 1)] colors and frequency range [σ/2, σ]. Its running times are T seq (Iter NBC) = O(m lg ∆) and T cc (Iter NBC) = O(lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (Iter NBC) = O(lg ∆ · (D + ∆ + lg5 lg n)) with high probability. Proof. We first prove that the loop runs for T = O(lg ∆) iterations. Let st be the number of Small colors at iteration t. By Lemma 4.1, the split step never creates small colors. By Lemma 4.2, Step 10 eliminates at least half of the existing small colors. Thus, st+1 ≤ st /2. At the beginning of each iteration, the palette before the split has size ∆ + 1, and the split step creates no new small colors; hence st ≤ ∆ + 1 whenever small colors remain. Therefore after O(lg ∆) iterations, Psmall = ∅. After the final split (Step 11), all colors satisfy f(i) ∈ [σ/2, σ]. The number of colors χ is bounded n n n by χ ≤ fmin ≤ σ/2 = 2(∆ + 1), and χ ≥ fmax ≥ nσ = ∆ + 1. The runtime statement follows by Fact 4.3 (see Section 9).

15

5

Near-Equitable Coloring with Palette - Frequency Range Tradeoff

In this section, we present a generalization that allows for a trade-off between the total number of colors and the maximum color frequency. By adjusting a parameter k ≥ 1, we achieve a coloring with at most (1 + 1/k)(∆ + 1) colors, where every color i has frequency f(i) ∈ [σ/2, 2kσ] in a total CC run-time of O(lg ∆) rounds. This approach leverages the balanced state produced by Algorithm 3 (Iter NBC) to aggressively reduce the palette size to ∆ + 1 before performing a final relaxed split.

5.1

Algorithm Description

The algorithm, named P-F Trade(G, k), first executes Algorithm Iter NBC (Algorithm 3) to obtain a high-quality equitable coloring. It then forces a reduction to exactly ∆+1 color classes (potentially creating large classes) and finally splits any class exceeding the relaxed threshold ⌈2kσ⌉. Algorithm 4: P-F Trade(G, k) 1 Input: Graph G = (V, E), parameter k ≥ 1. 2 Output: Valid coloring ϕ with frequency range [σ/2, 2kσ]. 3 ϕ ← Iter NBC(G)

▷ Returns ≤ 2(∆ + 1) classes, sizes in [σ/2, σ] 4 Sort colors in P by nonincreasing order of frequency: f(i1 ) ≥ f(i2 ) ≥ · · · ≥ f(im ). 5 Ptarget ← {i1 , . . . , i∆+1 } ▷ Select the ∆ + 1 most frequent colors S 6 Vtarget ← V (i) i∈P\Ptarget 7 Recolor(Vtarget , Ptarget ) ▷ Dissolve small classes into the top set 8 P ← Ptarget ▷ Palette size is now exactly ∆ + 1 9 fmax ← ⌈2kσ⌉ ▷ Final Relaxed Split 10 ϕ ← Split(ϕ, fmax ) 11 return ϕ

5.2

Correctness proof and analysis

We now verify the bounds for the frequency range and the palette size. Lemma 5.1. For k ≥ 1, the algorithm produces a coloring with frequency range [⌊σ/2⌋, ⌈2kσ⌉]. Proof. Step 9 of the algorithm sets fmax = ⌈2kσ⌉, so by Lemma 2.6, the upper frequency threshold is enforced explicitly by Step 10 of the algorithm. Turning to the lower bound, we analyze the frequencies before and after the split. After Step 3 (Algorithm 3 (Iter NBC)), all colors satisfy f(i) ≥ ⌊σ/2⌋. In the recoloring stage, the colors in Ptarget only absorb vertices from Vtarget , so their frequencies strictly increase. Thus, before the final split (Step 10), all colors in P satisfy f(i) ≥ ⌊σ/2⌋. In Step 10, a color i is split only if f(i) > ⌈2kσ⌉. By Lemma 2.6, splitting a color with upper threshold fmax = ⌈2kσ⌉ produces new colors with frequency     fmax ⌈2kσ⌉ = ≥ kσ ≥ ⌊σ/2⌋, (5) f(inew ) ≥ 2 2 16

where the penultimate inequality follows from ⌈2kσ⌉ ≥ 2kσ and the last one follows since k ≥ 1. Thus, both the unsplit colors and the newly split colors respect the lower frequency threshold ⌊σ/2⌋. Lemma 5.2. The number of color classes in the final coloring is at most (1 + 1/k)(∆ + 1). Proof. Prior to the final split, the algorithm compacts the coloring into exactly ∆ + 1 colors. The final phase splits only the colors in the set S = {i | f(i) > ⌈2kσ⌉}. When a color i ∈ S is split, let p = pi be the number of final colors descended from i. It introduces p − 1 additional colors. By Eq. (5) (or Lemma 2.6) and the integrality of fmax = ⌈2kσ⌉, each final descendant has frequency at least kσ. Therefore, f(i) ≥ p · kσ, which implies that the number of new colors contributed by this split is p − 1 < p ≤ f(i) kσ . Summing over all split colors, the total number of new colors, χnew , is P bounded by the total frequency n divided by the contribution of each split color, i.e., n n ∆+1 χnew < i∈S f(i) kσ ≤ kσ . Substituting σ = ∆+1 , we get χnew < k . Thus, the total number of colors is bounded by (∆ + 1) + ∆+1 k = (1 + 1/k)(∆ + 1). This theorem establishes a trade-off between the palette size and the maximum color frequency. While the iterative balanced coloring achieves a tight frequency balance of [σ/2, σ] at the cost of using up to 2(∆ + 1) colors, the generalized algorithm allows us to push the palette size arbitrarily close to the ideal lower bound of ∆ + 1 by increasing k. Crucially, this reduction in palette size does not compromise the lower threshold on frequencies; all color frequencies remain bounded below by σ/2. For the sake of the time analysis of Section 9 we note the following: Fact 5.3. After the initialization by Iter NBC, Algorithm P-F Trade performs one CA step to sort colors and choose Ptarget , one call to Recolor, and one final call to Split. The next theorem now follows from Lemmas 5.1, 5.2 and Fact 5.3. computes Theorem 5.4. For a graph G and an integer parameter
k ≥ 1, P-F Trade (Algorithm 4)  1 σ a valid coloring ϕ of G with palette size χ ≤ 1 + k (∆ + 1) and frequency range 2 , 2kσ . Its running times are T seq (P-F Trade) = O(m lg ∆) and T cc (P-F Trade) = O(lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (P-F Trade) = O(lg ∆ · (D + ∆ + lg5 lg n)) with high probability.

5.3

The SMALL Initialization Variant

A second instantiation of the same split & Recolor block uses the faster low-threshold initialization NBC (Algorithm 2) from Section 3. Define P-F TradeSMALL (G, k) to be the algorithm obtained from Algorithm 4 (P-F Trade) by replacing line 3 with the call ϕ ← NBC(G, 1/3). All subsequent lines are unchanged: the algorithm keeps the ∆ + 1 most frequent colors, recolors the deleted color classes into this target palette, and finally invokes Split with threshold fmax = ⌈2kσ⌉. For the sake of the time analysis of Section 9 we note the following: Fact 5.5. Algorithm P-F TradeSMALL has the same accounting as Fact 5.3, with the initialization Iter NBC replaced by NBC.

17

The proof of the following theorem goes along similar lines to that of Lemmas 5.1, 5.2 and Theorem 5.4, and is therefore omitted. Theorem 5.6. For a graph G and an integer
parameter k ≥ 1, P-F TradeSMALL computes a valid 1 coloring ϕ of G with palette size χ ≤ 1 + k (∆ + 1) and frequency range [σ/3, 2kσ]. Its running times are T seq (P-F TradeSMALL ) = O(m) and T cc (P-F TradeSMALL ) = O(1). In the CONGEST model, the coloring is obtained in time T cngst (P-F TradeSMALL ) = O(D + ∆ + lg5 lg n) with high probability.

6

Near-equitable coloring with Palette - Time Trade-off

In this section, we propose an algorithm that achieves a coloring with palette size at most (1 + 1/k)(∆ + 1) and frequency range [σ/2, 2σ]. This algorithm provides a middle ground between the tight palette of the exact (∆ + 1)-coloring and the speed of the earlier approximations. Specifically, by relaxing the palette constraint slightly by a factor of 1/k, we ensure the algorithm terminates in O(k) iterations, with total CC time complexity O(k + lg ∆) rounds.

6.1

Algorithm Description

Algorithm P-T Trade iteratively compacts the coloring into the largest ∆ + 1 classes and then handles overflows. It continues this process until the number of color classes falls within the target range. Algorithm 5: P-T Trade(G, k) 1 Input: Graph G = (V, E), parameter k ≥ 1. 2 Output: Valid coloring ϕ with ≤ (1 + 1/k)(∆ + 1) colors, sizes in [σ/2, 2σ].

▷ Initial coloring: ≤ 2(∆ + 1) colors

3 ϕ ← Iter NBC(G) 4 fmax ← 2σ 5 while χ > (1 + 1/k)(∆ + 1) do 6 7 8 9 10

Sort colors in P by nonincreasing order of frequency: f(i1 ) ≥ f(i2 ) ≥ · · · ≥ f(im ). Ptarget ← S {i1 , . . . , i∆+1 } Vtarget ← i∈P\Ptarget V (i) Recolor(Vtarget , Ptarget ) ϕ ← Split(ϕ, fmax )

11 return ϕ

6.2

Correctness proof and analysis

We first verify that the color frequencies remain within the desired range following each execution of Procedure Split throughout the run. Lemma 6.1. In any execution of P-T Trade (Algorithm 5), following each invocation of Procedure Split, every color i satisfies f(i) ∈ [σ/2, 2σ]. Proof. The initial coloring (Iter NBC, Algorithm 3) satisfies the bounds [σ/2, σ] ⊂ [σ/2, 2σ]. In the recoloring step, vertices are added to existing colors, so their frequencies only increase; thus, the 18

lower bound σ/2 is preserved. In the splitting step, any color with f(i) > 2σ is split. By Lemma 2.6, splitting a color with f(i) > 2σ results in new colors with frequency at least ⌊f(i)/2⌋ ≥ σ. Since σ > σ/2, the lower bound is preserved. Finally, the splitting process explicitly enforces the upper bound 2σ at the end of every iteration. We now analyze the convergence rate, proving that the algorithm terminates quickly. Lemma 6.2. Algorithm P-T Trade terminates in O(k) iterations. Proof. To prove the iteration bound, we categorize colors based on their frequency relative to σ. For this analysis only, define a color i as large if f(i) ≥ σ and small otherwise. The total number of vertices in the graph is n = (∆ + 1)σ. Since every large color has f(i) ≥ σ, the number of large colors at any point in the execution is bounded by N large ≤ n/σ = ∆ + 1.

(6)

We now track the number of small colors, denoted Ntsmall , at the beginning of iteration t. We analyze the two steps of the loop. In each iteration, the algorithm retains the ∆ + 1 most frequent colors and dissolves the rest. The loop condition ensures the current total number of colors is χt > (1 + 1/k)(∆ + 1). The number of dissolved colors is: N dissolved = χt − (∆ + 1) >

1 (∆ + 1). k

By Eq. (6), the ∆ + 1 highest frequency colors must include all existing large colors. Consequently, all N dissolved colors that are dropped must be small colors. The algorithm splits colors with f(i) > 2σ. By Lemma 2.6, splitting such a color creates new colors with frequency at least σ. Thus, the splitting process never creates a small color. Combining these observations, the number of small colors strictly decreases in each iteration. Specifically, at least (∆ + 1)/k small colors are removed in the recoloring stage, and no small colors are added in the splitting step. Hence, st+1 ≤ st − (∆ + 1)/k. The initial coloring by Algorithm Iter NBC(G) uses at most 2(∆ + 1) colors, so s0 ≤ 2(∆ + 1). It follows that the maximum number s0 of iterations satisfies (∆+1)/k = O(k). For the sake of the time analysis of Section 9 we note the following: Fact 6.3. Algorithm P-T Trade first invokes Iter NBC. By Lemma 6.2, it then performs O(k) loop iterations, each containing one CA step for sorting and selecting the retained palette, one call to Recolor, and one call to Split. Theorem 6.4. For every k ≥ 1, Algorithm 5 (P-T Trade) returns a valid coloring with at most (1 + 1/k)(∆ + 1) colors and frequency range [σ/2, 2σ]. Its running times are T seq (P-T Trade) = O(m(k + lg ∆)) and T cc (P-T Trade) = O(k + lg ∆). In the CONGEST model, the coloring is obtained in time T cngst (P-T Trade) = O((lg ∆ + k) · (D + ∆ + lg5 lg n)) with high probability. Proof. The bound on the palette size follows from the stopping condition of the loop, and the frequency range bounds follow from Lemma 6.1. The runtime statement follows from Fact 6.3 and is calculated in Section 9. 19

6.3

The SMALL Initialization Variant

A replacement similar to that of Section 5.3 gives a faster low-threshold version of the palette-time tradeoff algorithm. Define P-T TradeSMALL (G, k) to be the algorithm obtained from Algorithm 5 (P-T Trade) by replacing line 3 with the call ϕ ← NBC(G, 1/3). The stopping threshold (1 + 1/k)(∆ + 1), the repeated recoloring to the ∆ + 1 largest colors, and the split threshold fmax = 2σ are left unchanged. For the sake of the time analysis of Section 9 we note the following: Fact 6.5. Algorithm P-T TradeSMALL first invokes NBC. Since the NBC(G, 1/3) initialization starts with at most 3(∆ + 1) colors, and every loop iteration dissolves at least (∆ + 1)/k colors before the split, the algorithm performs O(k) loop iterations. Each iteration contains one CA step, one call to Recolor, and one call to Split. The proof of the following theorem goes along similar lines to that of Lemmas 6.1, 6.2 and Theorem 6.4, and is therefore omitted. Theorem 6.6. For every k ≥ 1, P-T TradeSMALL returns a valid coloring with at most (1 + 1/k)(∆ + 1) colors and frequency range [σ/3, 2σ]. Its running times are T seq (P-T TradeSMALL ) = O(mk) and T cc (P-T TradeSMALL ) = O(k). In the CONGEST model, the coloring is obtained in time T cngst (P-T TradeSMALL ) = O(k · (D + ∆ + lg5 lg n)) with high probability.

7

Capped palette reduction

This section presents Algorithm Open Recolor, which refines our previous approach to the palettereduction step. Starting from the basic Iter NBC coloring of Section 4, it reduces the palette from at most 2(∆ + 1) colors to β(∆ + 1), where 1 < β < 2, while preserving frequencies throughout the process in the range [σ/2, fmax ] for the integer cap fmax = ⌈ασ⌉.

7.1

Overview and goal

Let us start with describing the main idea for the improved solution. Algorithm Iter NBC (Section 4) was based on alternating between recoloring phases, which reduced the number of colors at the cost of increasing the frequencies of the remaining colors, and splitting phases, which increased the number of colors. The idea at the basis of the new approach is to prevent the need for splitting, thus reducing the number of phases. To achieve that, we no longer treat all colors with frequency ≤ fmax as valid targets in the recoloring stage. Rather, we forbid the use of a color c if its frequency f(c) is so close to fmax that there’s a risk that it might exceed fmax if c is used in the recoloring stage. Concretely, we fix a threshold fcap = φ · fmax for a suitably chosen constant 12 < φ < 1, such that colors whose frequency falls in the range [fcap , fmax ] are considered closed and cannot be used for recoloring. An uncolored vertex v cannot choose a color already used by a colored neighbor, i.e., a color from Pneig (v) = {ϕ(u) | u ∈ N (v) \ Vtarget },

20

so its nonconflicting palette is Ptarget (v) = Ptarget \ Pneig (v) .

(7)

Moreover, it must obey the additional capping restriction, namely, it is only allowed to select an open color c ∈ Ptarget (v), namely, such that f(c) < fcap . This condition by itself does not guarantee that the resulting coloring will obey the upper frequency threshold fmax , as it might happen that many pairwise non-adjacent uncolored vertices select the same open color c, causing f(c) to exceed fmax . To overcome this difficulty, the algorithm imposes the threshold fmax deterministically; it counts the number of vertices that selected the color c, and allows only fmax −f(c) uncolored vertices to use it. The remaining vertices remain uncolored and will try again in subsequent recoloring iterations. A natural concern is that this might run the risk of leaving some vertices uncolored forever. As shown in our analysis, a careful choice of the threshold fcap ensures that this risk never materializes, and every uncolored vertex gets recolored eventually.

7.2

Parameters and algorithm

Let β = 1 + ℓ/(∆ + 1), where 1 ≤ ℓ ≤ ∆, and use the integer cap fmax = ⌈ασ⌉. The target palette has size χtarget = β(∆ + 1) = ∆ + 1 + ℓ colors. Algorithm Open Recolor deletes the least frequent colors and recolors their vertices into the retained target palette. For an open-capacity parameter φ ∈ (0, 1), set fcap = ⌊φασ⌋ and use the capacity gap fmax − fcap . Vertices propose only open colors in Ptarget (v). Once candidates for color c are listed, the algorithm accepts at most fmax − f(c) of the candidates (namely, allows them to use the color) and rejects the others. The parameters used in this section are required to satisfy the following conditions: ℓ β = 1 + ∆+1

for an integer 1 ≤ ℓ ≤ ∆,

hence 1 < β < 2,

(8)

α ≥ 1,

(9)

1 2 < φ < 1, ℓ 2φα · ∆+1 > 1.

(10) (11)

Since fmax is a positive integer, φ < 1 and fcap is rounded down, fmax − fcap ≥ 1. The activation probability p0 is chosen from the same parameters and defined in Algorithm 6 (Open Recolor). Algorithm 6 (Open Recolor) gives the formal code.

21

Algorithm 6: Open Recolor(G, α, β, φ) 1 Input: graph G = (V, E),

parameters α, β, φ where β = 1 + ℓ/(∆ + 1). 2 Output: a valid coloring with at most χtarget = ∆ + 1 + ℓ colors, and frequencies ∈ [σ/2, ⌈ασ⌉]. 3 Setup and palette reduction. 4 ϕ ← Iter NBC(G) (frequencies in [σ/2, σ]) 5 fmax ← ⌈ασ⌉, fcap ← ⌊φασ⌋ 2−β 6 δ ← β − 1 − 2φα−1 1 7 p0 ← 2 min{1, δ, δ(1 − φ)α/(1 − β/2)} 8 χtarget ← β(∆ + 1) = ∆ + 1 + ℓ 9 if χ ≤ χtarget then 10 return ϕ 11 Sort colors so that f(i1 ) ≤ · · · ≤ f(iχ ) 12 χremove ← χ − χtarget 13 Premove ← {i1 , . . . , iχremove } S 14 Vtarget ← i∈Premove V (i) 15 Ptarget ← P \ Premove 16 Unset the colors of all vertices in Vtarget

7.3

17 Open recoloring phase. 18 while Vtarget ̸= ∅ do 19 Popen ← {c ∈ Ptarget | f(c) ≤ fcap } 20 for each v ∈ Vtarget in parallel do 21 Pneig (v) ← {ϕ(u) | u ∈ N (v) \ Vtarget } 22 Ptarget (v) ← Ptarget \ Pneig (v) 23 Popen (v) ← Ptarget (v) ∩ Popen 24 Become active with probability p0 25 if v is active and Popen (v) ̸= ∅ then 26 Pick cv ∈ Popen (v) uniformly at random

and broadcast Propose(cv ) If no neighbor in Vtarget proposes cv , then v becomes a candidate for color cv 28 for each color c ∈ Ptarget in parallel do 29 Let Cc be the candidates for c 30 Draw a fresh random ranking for the vertices of Cc . 31 Ccadd ← the set of min{|Cc |, fmax − f(c)} highest-ranked candidates 32 For every v ∈ Ccadd S , set ϕ(v) ← c 33 Vtarget ← Vtarget \ c∈Ptarget Ccadd 34 Update all frequencies 35 return ϕ

27

Correctness proof and analysis

Observation 7.1. For δ and p0 as defined in Algorithm 6 (Open Recolor), the quantities fmax , fcap , δ, p0 are well-defined, fmax − fcap ≥ 1, δ > 0, and 0 < p0 ≤ 1/2. Proof. By Conditions (9) and (10), the denominator 2φα − 1 in the definition of δ is positive. Moreover, since β − 1 = ℓ/(∆ + 1), δ = β−1−

2φα(β − 1) − 1 2−β = > 0, 2φα − 1 2φα − 1

(12)

where the final inequality follows since Condition (11) gives 2φα(β − 1) > 1. The denominator in the third term in the definition of p0 in Algorithm 6 (Open Recolor) is positive because β < 2 by Eq. (8). Since fmax is a positive integer and φ < 1, we have fcap = ⌊φασ⌋ ≤ fmax − 1, and hence fmax − fcap ≥ 1. Consequently, Conditions (8)–(11) yield the claims. Lemma 7.2. At every point in Algorithm 6 (Open Recolor), the partial coloring is valid and every target color c ∈ Ptarget satisfies f(c) ≤ fmax . Consequently, if the procedure terminates, it returns a valid coloring whose target-color frequencies are at most fmax . Proof. A vertex proposes only a color not used by any already-colored neighbor. Two adjacent uncolored vertices proposing the same color cannot both become candidates, because both detect a conflict. Hence accepting candidates preserves the validity of the coloring. For the upper bound, fix a color c and an iteration. The algorithm accepts at most fmax − f(c) candidates for c, so after the round its frequency is still at most fmax . This proves the invariant by induction over the iterations. 22

Lemma 7.3. After the palette-reduction step of Algorithm 6 (Open Recolor), |Vtarget | ≤ (1−β/2)n. Proof. The target palette has size χtarget = β(∆ + 1). Each retained target color has frequency at least σ/2, because the input coloring from Iter NBC has frequencies in [σ/2, σ]. Thus the number of vertices colored by the retained colors satisfies f(Ptarget ) ≥ χtarget ·

σ σ βn = β(∆ + 1) · = . 2 2 2

All other vertices are placed in Vtarget . Lemma 7.4. Assume Conditions (8)–(11), and let δ be the value defined in Algorithm 6 (Open Recolor). In every round of Algorithm 6 (Open Recolor), every uncolored vertex v satisfies |Popen (v)| ≥ δ(∆ + 1) + 1. Proof. Fix an iteration, and let Pclosed = Ptarget \ Popen . Every c ∈ Pclosed satisfies f(c) > φασ because fcap = ⌊φασ⌋ and frequencies are integral. Every target color has frequency at least σ/2, since target colors are never dissolved and only gain vertices. Therefore, n ≥ χclosed · φασ + (χtarget − χclosed ) ·

σ . 2

Substituting χtarget = β(∆ + 1), dividing by σ and rearranging gives χclosed ≤

2−β 1 − β/2 (∆ + 1) = (∆ + 1). φα − 1/2 2φα − 1

(13)

The set Pneig (v) of colors used by v’s colored neighbors is of size χneig (v) ≤ ∆, so by Eq. (7), χtarget (v) satisfies χtarget (v) ≥ χtarget − ∆ = (β − 1)(∆ + 1) + 1. (14) By Eq. (13) and (14), χopen (v) ≥ χtarget (v) − χclosed ≥

  2−β (∆ + 1) + 1 = δ(∆ + 1) + 1 β−1− 2φα − 1

by the definition of δ. For a recoloring round t, let Histt denote the history of the execution up to the beginning of round t. Let EGoodHist (t) be the event that no bad event occurred in iterations 1, . . . , t − 1, where a bad event means that (a) the partial coloring became invalid, (b) some target color exceeded the cap fmax , or (c) some uncolored vertex had fewer than δ(∆ + 1) + 1 open locally valid colors at the beginning of an iteration. We observe that any history Histt reached by Algorithm 6 (Open Recolor) by the end of round t − 1 satisfies EGoodHist (t) deterministically. This can be verified by induction on t. For t = 1, note that before the first recoloring round, uncolored vertices cannot create a conflict among the vertices that remain colored, all target colors have frequency at most σ ≤ fmax , and Lemma 7.4 establishes condition (c) in the definition of EGoodHist (t). For the inductive step, assuming that Histt satisfies EGoodHist (t), Lemma 7.2 shows that round t preserves conditions (a) and (b), and Lemma 7.4 establishes condition (c) for the resulting history Histt+1 . 23

In the next lemma, conditioning on a fixed history Histt (which satisfies EGoodHist (t) as shown above), the partial coloring, the uncolored set, all frequencies, and all palettes are fixed; the only remaining randomness is the fresh random choices made in round t. Lemma 7.5. Assume Conditions (8)–(11), and set p0 as in Algorithm 6 (Open Recolor). For every round t and every history Histt , each vertex that is still uncolored at the beginning of round t becomes colored in that round with conditional probability at least p0 /4. Proof. Fix an iteration t, condition on a history Histt (which satisfies EGoodHist (t) as shown above), and fix an uncolored vertex v. In this proof all probabilities and expectations are with respect to the random choices made in round t, conditioned on this history. Set A = δ(∆ + 1) + 1. By Lemma 7.4, χopen (v) ≥ A. Let Eactive (v) be the event that v is active. For any uncolored vertex x and color c, let Ex→c be the event that x is active and proposes c in this round. This event already includes activation, so no additional conditioning on Eactive (x) is used in the proposal bounds. Fix a color c ∈ Popen (v). For any uncolored neighbor u, P[Eu→c | Ev→c ] ≤ pA0 . Indeed, if c ∈ / Popen (u) then this probability is 0, and otherwise it is at most p0 /|Popen (u)| ≤ p0 /A. By the union bound over at most ∆ < ∆ + 1 neighbors, p0 p0 1 P[v has a proposal conflict | Ev→c ] ≤ ∆ · > ≤ , (15) A δ 2 where the last inequality follows from Eq. (12) and the definition of p0 in Algorithm 6 (Open Recolor), which gives p0 ≤ δ/2. Hence, conditioned on Ev→c , vertex v becomes a candidate with probability at least 1/2. It remains to bound the probability that color c accepts v. Let Y be the number of uncolored vertices outside N (v) ∪ {v} that propose c in this round. By Lemma 7.3, the current uncolored set has size at most (1 − β/2)n. For every such vertex w, P[Ew→c | Ev→c ] ≤

p0 . A

Therefore

(1 − β/2)σp0 p0 ≤ . A δ By the definition of p0 in Algorithm 6 (Open Recolor), E[Y | Ev→c ] ≤ (1 − β/2)n ·

1 E[Y | Ev→c ] ≤ (1 − φ)ασ. 2 Since fmax − fcap = ⌈ασ⌉ − ⌊φασ⌋ ≥ ασ − φασ = (1 − φ)ασ, Markov’s inequality gives P[Y ≥ fmax − fcap | Ev→c ] ≤

E[Y | Ev→c ] 1 ≤ . fmax − fcap 2

(16)

The random choices of vertices outside N (v) ∪ {v} are independent of the random choices of the uncolored neighbors of v, conditioned on Ev→c . Because c is open, its remaining capacity is at least fmax − fcap . If no neighbor of v proposes c and Y < fmax − fcap , then even after including v, at 24

most fmax − fcap vertices propose c. Thus all candidates for c can be accepted, and in particular v is accepted. Therefore, by Eqs. (15) and (16), conditioned on Ev→c , the probability that v is colored is at least 1/4. This lower bound is uniform over all possible choices c ∈ Popen (v). Hence, by the law of total probability over the random color chosen by v, conditioned only on v being active, the probability that v is colored is also at least 1/4. Multiplying by the activation probability p0 , the one-round success probability is at least p0 /4. The preceding lemmas establish the deterministic safety, the availability of open colors, and the one-round progress bound. We now combine them into the parameterized guarantee for Algorithm 6 (Open Recolor), and then derive the asymptotic palette–frequency tradeoff as two corollaries. For the sake of the time analysis of Section 9 we note the following: Fact 7.6. Algorithm Open Recolor first invokes Iter NBC. By Lemma 7.5, with high probability it then performs O(lg n/p0 ) open-capacity iterations. Each such iteration updates open colors and frequencies using CA and admits candidates according to the residual capacities using QA. The local proposal and conflict-test operations are handled within these iterations and do not introduce an additional primitive in the accounting of Section 9. When α, β, φ are fixed admissible constants, p0 = Ω(1) and this factor disappears.

Theorem 7.7. For parameters satisfying conditions (8)–(11), Algorithm 6 (Open Recolor) returns a valid coloring with at most β(∆+1) = ∆+1+ℓ colors and frequency range [σ/2,⌈ασ⌉]. Its running times are T seq (Open Recolor) = O(m(lg ∆+lg n/p0 )), T cngst (Open Recolor) = O lg ∆ · (D + ∆ + lg5 lg n) + (D + ∆ and T cc (Open Recolor) = O(lg ∆+lg n/p0 ). If α is a fixed constant, these simplify to T seq (Open Recolor) = O(m lg n), T cngst (Open Recolor) = O((D +∆) lg n+lg ∆·lg5 lg n) and T cc (Open Recolor) = O(lg n), with high probability. Proof. The call to Iter NBC returns frequencies in [σ/2, σ]. If Algorithm Open Recolor returns immediately, the theorem follows from α ≥ 1. Otherwise, the algorithm keeps exactly β(∆ + 1) target colors. These colors had frequency at least σ/2 before recoloring and only gain vertices, so the lower bound is preserved. Since they start with frequency at most σ ≤ ασ ≤ fmax , Lemma 7.2 gives validity and the upper bound fmax = ⌈ασ⌉. As observed above, every history reached by Algorithm 6 (Open Recolor) satisfies EGoodHist (t). Thus Lemma 7.5 applies in every round: conditioned on the history, each still uncolored vertex is colored with probability at least p0 /4. Iterating this conditional bound, for any fixed vertex v and any T ≥ 4(c + 1) ln n/p0 , the probability that v remains uncolored is at most (1 − p0 /4)T ≤ n−(c+1) . A union bound over all vertices gives termination after O(lg n/p0 ) recoloring iterations with probability at least 1 − n−c . For fixed admissible α, β, φ, the definition of p0 has only positive constant terms, hence p0 = Ω(1). The runtime statement follows from Fact 7.6 and is calculated in Section 9. We now consider what happens when ℓ tends to zero. Let ϵ > 0 be a constant, let α ≥ 1, and let φ satisfy 1 < 1 + 2ϵ ≤ 2α∆/(∆ + 1), n o 1 max 12 , 1+2ϵ < φ < 1. 25

(17) (18)

Set ρ(α) = (1 + 2ϵ)/(2α) and ℓϵ = ⌈ρ(α)(∆ + 1)⌉. Corollary 7.8. Algorithm 6 (Open Recolor), run with ℓ = ℓϵ and β = 1+ℓϵ /(∆+1), returns a valid coloring with frequency range [σ/2, ⌈ασ⌉] and palette size χ ≤ (1 + ρ(α))(∆ + 1) + 1. The running times are T seq (Open Recolor) = O(m lg n), T cngst (Open Recolor) = O((D + ∆) lg n + lg ∆ · lg5 lg n) and T cc (Open Recolor) = O(lg n), with high probability. Proof. By Eq. (17), ℓϵ ≤ ∆, so Condition (8) holds for β = 1 + ℓϵ /(∆ + 1). Conditions (9) and (10) hold by the assumptions of the corollary. Moreover, 2φα(β − 1) = 2φα ·

ℓϵ ≥ 2φα · ρ(α) = φ(1 + 2ϵ) > 1, ∆+1

(19)

where the last inequality follows from Eq. (18). Thus Condition (11) also holds, and Theorem 7.7 applies. The palette bound follows from χ ≤ ∆ + 1 + ℓϵ ≤ (∆ + 1) + ρ(α)(∆ + 1) + 1 = (1 + ρ(α))(∆ + 1) + 1. It remains only to note that p0 = Ω(1) for these constant parameters. By Eq. (12) and (19), δ=

2φα(β − 1) − 1 φ(1 + 2ϵ) − 1 ≥ > 0, 2φα − 1 2φα − 1

and the right-hand side is a positive constant. Since 1 − β/2 ≤ 1/2, the third term in the definition of p0 is also bounded below by a positive constant. Hence p0 = Ω(1). The running times are obtained from Fact 7.6 by the substitutions carried out in Section 9. By way of a concrete example, fix a constant 0 < ϵ < 1/2, consider graphs satisfying 1 + 2ϵ ≤ 2∆/(∆ + 1), and fix a constant φ satisfying 1/(1 + 2ϵ) < φ < 1. Then we get the following. Corollary 7.9. Algorithm 6 (Open Recolor), run with α = 1 and ℓ = ⌈(1/2 + ϵ)(∆ + 1)⌉, returns a valid coloring with at most (1.5 + ϵ)(∆ + 1) + 1 colors and frequency range [σ/2, ⌈σ⌉]. Its running times are T seq (Open Recolor) = O(m lg n), T cngst (Open Recolor) = O((D + ∆) lg n + lg ∆ · lg5 lg n) and T cc (Open Recolor) = O(lg n), with high probability.

8

∆+1 Palette Reduction with a Logarithmic frequency threshold

Section 7 gave a capped recoloring procedure that reduces the palette to β(∆ + 1) = ∆ + 1 + ℓ colors. Its progress condition, Eq. (11), requires 2φαℓ/(∆ + 1) > 1. Hence pushing that one-shot reduction all the way to ∆ + 1 colors would force α = Ω(∆) and give no useful near-equitable bound. This section handles the χ = ∆ + 1 endpoint by applying the same capped recoloring idea gradually. Starting from the balanced coloring produced by Iter NBC, the algorithm repeatedly deletes a constant fraction of the current excess colors and recolors the deleted vertices into the remaining palette. In each phase, every surviving color (that is still in P) may receive only O(σ) additional vertices. Since the excess decreases geometrically, the number of phases is O(lg ∆). The 26

resulting price for reaching ∆ + 1 colors is therefore an upper frequency threshold of order σ lg ∆, rather than an O(σ) threshold. For fixed parameters ε and c, set Cε = 100/ε. Throughout this section, assume the requirements 0 < ε ≤ 1,

c ≥ 1,

σ ≥ max{6/ε, Cε (c + 6) lg n}.

(20)

Let fph max = ⌈(1 + ε)σ⌉

and

fmax = σ + ⌈lg(∆ + 1)⌉ · fph max .

The main result of the section is that Algorithm 7 (LogCap Compact) computes, with probability at least 1 − n−c a valid coloring with at most ∆ + 1 colors in O(lg n lg ∆) CC rounds. The lower frequency threshold remains σ/2, and the upper frequency threshold is fmax = O(lg ∆ · σ).

8.1

Overview and Goal

Algorithm 7 (LogCap Compact) starts by applying the capped recoloring idea of Section 7 in phases, to achieve χ = ∆ + 2. In one phase, it removes the χremove = ⌊χexcess /2⌋ least frequent colors and recolors their vertices into the remaining target palette by calling Algorithm 8 (Budget Recolor). The call to Budget Recolor enforces an individual phase budget rather than a global frequency cap. At the beginning of the phase, each target color has counter fadd (i) = 0; during the phase it may color at most fph max = ⌈(1 + ε)σ⌉ new vertices. A target color i is open in a recoloring iteration t only if at the beginning of the iteration, fadd (i) ≤ fcap = ⌊(1 + ε/2)σ⌋. Note that if i is open in iteration t, it might accept more than fcap − fadd (i) new candidates, making it closed for the remaining iterations of the current phase, but the algorithm enforces that it will not “overflow” ph beyond the absolute threshold fph max in the current iteration. We refer to Bi = fmax − fadd (i) as the budget of color i for the remainder of the current phase. The gap of fph max − fcap = Ω(εσ) unused colors is used in the concentration argument. Since each phase removes a constant fraction of the current excess palette of χ − (∆ + 1) colors, and χ = O(∆), there are O(lg ∆) phases. Each “surviving” color (that remains in P) receives only O(σ) new vertices per phase. It follows that the upper frequency threshold is only fmax = O(lg ∆·σ). The algorithm concludes with applying one final step of Recolor, discarding the smallest frequency color and ending with an optimal palette size of ∆ + 1. The formal descriptions of LogCap Compact and Budget Recolor appear in Algorithms 7 and 8.

8.2

Analysis

The next lemma is the phase-budget analogue of Lemma 7.2; the proof is the same deterministic safety argument, with the per-phase counter fadd (i) replacing the global frequency f(i). Lemma 8.1. At every point in Algorithm 8 (Budget Recolor), the partial coloring is valid and every target color i ∈ Ptarget satisfies fadd (i) ≤ fph max . Consequently, if the procedure terminates, it returns a valid extension of the input coloring and each target color receives at most fph max = ⌈(1+ε)σ⌉ new vertices during the phase.

27

Algorithm 7: LogCap Compact 1 Input: graph G = (V, E) with maximum degree ∆, constants 0 < ε ≤ 1 and c ≥ 1. 2 Output: a valid coloring with at most ∆ + 1 colors and frequency range [σ/2, 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉]. 3 ϕ ← Iter NBC(G) (χ ≤ 2(∆ + 1) and

Algorithm 8: Budget Recolor 1 Input: graph G = (V, E), target vertices Vtarget , current partial coloring ϕ, target palette Ptarget . 2 Parameters: thresholds fph max and fcap , activation probability p0 . 3 Output: a valid extension of ϕ to Vtarget . 4 For every i ∈ Ptarget set fadd (i) ← 0. 5 while Vtarget ̸= ∅ do 6 Popen ← {i ∈ Ptarget | fadd (i) ≤ fcap }. 7 for each v ∈ Vtarget in parallel do 8 Pneig (v) ← {ϕ(u) | u ∈ N (v) \ Vtarget }. 9 Ptarget (v) ← Ptarget \ Pneig (v). 10 Popen (v) ← Ptarget (v) ∩ Popen . 11 Become active with probability p0 . 12 if v is active and Popen (v) ̸= ∅ then 13 Pick cv ∈ Popen (v) uniformly at random and broadcast Propose(cv ). 14 If no neighbor in Vtarget proposes cv , then v becomes a candidate for color cv . 15 for each color i ∈ Ptarget in parallel do 16 Let Ci be the set of candidates for i. 17 Draw a fresh random ranking for the vertices of Ci . 18 Let Bi ← fph max − fadd (i). 19 Ciadd ← the min{|Ci |, Bi } highest-ranked candidates. 20 For every v ∈ Ciadd , set ϕ(v) ← i. 21 fadd (i) ← fadd (i)S+ |Ciadd |. 22 Vtarget ← Vtarget \ i∈Ptarget Ciadd . 23 return ϕ.

f(i) ∈ [σ/2, σ]) 4 while χ > ∆ + 2 do 5 χexcess ← χ − (∆ + 1). 6 χremove ← ⌊χexcess /2⌋. 7 Sort colors by nondecreasing frequency:

f(i1 ) ≤ · · · ≤ f(iχ ). Premove ←S{i1 , . . . , iχremove }. Vtarget ← i∈Premove V (i). Ptarget ← P \ Premove . Cancel the colors of all vertices in Vtarget . fph max ← ⌈(1 + ε)σ⌉, fcap ← ⌊(1 + ε/2)σ⌋, p0 ← ε2 /16. 13 Run Budget Recolor on G, ϕ, Vtarget , Ptarget with parameters fph max , fcap , p0 . 14 Set ϕ to the output of this call. 15 end while (χ = ∆ + 2) 16 Sort current colors by nonincreasing frequency: f(i1 ) ≥ · · · ≥ f(iχ ). 17 Ptarget ← {i1 , . . . , i∆+1 }. 18 Vtarget ← Viχ . 19 Cancel the color iχ . 20 ϕ ← Recolor(Vtarget , Ptarget ) 21 return ϕ.

8 9 10 11 12

Proof. A vertex proposes only a color not used by any already colored neighbor. If two adjacent uncolored vertices propose the same color, then neither of them becomes a candidate. Hence, accepting a candidate preserves validity. For the frequency threshold, fix a color i and an iteration of Algorithm 8 (Budget Recolor). The algorithm allows at most fph max − fadd (i) candidates to use the color i, so after the iteration, ph fadd (i) ≤ fmax . The claim follows by induction over the iterations. Lemma 8.2. In a phase of Algorithm 7 (LogCap Compact), let χremove = ⌊χexcess /2⌋.Then |Vtarget | = f(Premove ) ≤ χremove · σ. Proof. The average frequency over the current palette satisfies n/χ ≤ n/(∆+1) = σ. Since Premove consists of the χremove least frequent colors, its average frequency is at most the global average. Therefore f(Premove ) ≤ χremove · σ. The following lemma uses the same open/closed palette counting template as Lemma 7.4; here the phase parameter s and the counters fadd (i) replace the fixed target-palette parameters of Section 7. 28

t For an execution of Procedure Budget Recolor, let Vtarget be the set Vtarget at the beginning of t iteration t, and let dunc (v) be the number of neighbors of v that are still uncolored at the beginning t t of iteration t. Let Pneig (v) and Popen (v) be the sets Pneig (v) and Popen (v) constructed for the t t uncolored vertex v in Steps 8 and 10 of iteration t, respectively. Let Pclosed = Ptarget \ Popen .

Lemma 8.3. Consider a call to Algorithm 8 (Budget Recolor) with χtarget = ∆+1+s and |Vtarget | ≤ t sσ for some integer s ≥ 1. Assume Condition (20) holds. In every iteration t, Popen (v) satisfies t t χopen (v) ≥ dunc (v) + 1 + εs/4. t Proof. At any iteration t, the set Pneig (v) has size χtneig (v) ≤ ∆ − dtunc (v), so by Eq. (7),

χttarget (v) ≥ χtarget − χtneig (v) ≥ (∆ + 1 + s) − (∆ − dtunc (v)) = dtunc (v) + s + 1.

(21)

A color i that is closed at the beginning of iteration t satisfies fadd (i) > fcap . Since fcap = ⌊(1 + ε/2)σ⌋ and σ ≥ 6/ε by Eq. (20), we have fcap ≥ (1 + ε/3)σ, so at the beginning of iteration t, each closed color i has fadd (i) > (1 + ε/3)σ. 1 Note that the vertices that were colored during the phase all come from Vtarget , so at the beginning of iteration t, P 1 | ≤ sσ. fadd (i) ≤ |Vtarget χtclosed · (1 + ε/3)σ < i∈P t closed

Hence, the number of currently closed colors satisfies χtclosed ≤

 sσ ε ≤ 1− s. (1 + ε/3)σ 4

(22)

The last inequality follows since (1 − ε/4)(1 + ε/3) = 1 + ε(1 − ε)/12 ≥ 1 for 0 < ε ≤ 1. By Eq. (21) and (22), χtopen (v) ≥ χtarget (v) − χtclosed ≥ dtunc (v) + 1 + εs/4. The conditioning convention below is the same as the one used before Lemma 7.5; only the phasespecific bad events and the resulting one-iteration progress estimate change. For the next lemma, fix one call to Algorithm 8 (Budget Recolor). For a recoloring iteration t, let Histt denote the history of the execution up to the beginning of iteration t. Let EGoodHist (t) be the event that no bad event occurred in iterations 1, . . . , t − 1, where a bad event means that (a) the partial coloring became invalid, (b) some target color i satisfied fadd (i) > fph max , or (c) some uncolored vertex v had fewer than drunc (v) + 1 + εs/4 open locally valid colors at the beginning of some earlier iteration r < t. We observe that any history Histt reached by Algorithm 8 (Budget Recolor) by the end of iteration t − 1 satisfies EGoodHist (t). This is verified by induction on t. For t = 1, the input partial coloring is valid, all counters fadd (i) are zero, and Lemma 8.3 gives the open-choice bound. For the inductive step, Lemma 8.1 preserves validity and the bound fadd (i) ≤ fph max , and Lemma 8.3 gives the open-choice bound for the next history. In the next proof, we condition on a fixed history Histt satisfying EGoodHist (t). Under this conditioning, the partial coloring, the uncolored set, the counters fadd (i), and all palettes are fixed; the only remaining randomness is the fresh random choices made in iteration t. For readability, we omit this conditioning from the notation and write simply P[E ′ ] and E[X] instead of P[E ′ | EGoodHist (t)] and E[X | EGoodHist (t)]. 29

Lemma 8.4. Fix 0 < ε ≤ 1, Cε = 100/ε and c ≥ 1 satisfying Condition Eq. (20). Suppose Algorithm 8 (Budget Recolor) is called with χtarget = ∆ + 1 + s for an integer s ≥ 1, 2 |Vtarget | ≤ sσ, fph max = ⌈(1 + ε)σ⌉, fcap = ⌊(1 + ε/2)σ⌋, and p0 = ε /16. Then, with probability at least 1 − n−(c+2) , Algorithm 8 (Budget Recolor) terminates in O(ε−2 (c + 4) lg n) iterations, it returns a valid coloring for G and each color i ∈ Ptarget receives at most fph max new vertices during the phase.   Proof. Let T0 = 64ε−2 (c + 4) lg n . We prove that, with probability at least 1−n−(c+2) , all vertices of Vtarget are colored during the first T0 iterations. The validity of the coloring and the bound on the number of vertices added to each target color then follow from Lemma 8.1. We first control the event that too many vertices propose the same open color in one iteration. Fix an iteration t ≤ T0 , condition on a history Histt satisfying EGoodHist (t), and fix an open color i ∈ Popen . Let Yi,t be the number of active vertices that propose color i in iteration t, before conflict resolution. By Lemma 8.3, every vertex that can propose i has at least 1 + εs/4 open locally valid choices, and therefore proposes i with probability at most p0 /(1 + εs/4). Since |Vtarget | ≤ sσ, µ := E[Yi,t ] ≤

4p0 ε p0 p0 sσ · |Vtarget | ≤ ≤ σ = σ. 1 + εs/4 1 + εs/4 ε 4

On the other hand, since i is open, fadd (i) ≤ fcap , and hence its remaining budget satisfies ε ph Bi = fph max − fadd (i) ≥ fmax − fcap ≥ σ. 2 Thus Bi ≥ 2µ. If µ = 0, then Yi,t = 0 deterministically. Otherwise, applying the Chernoff bound to the threshold Bi gives P[Yi,t > Bi ] ≤ exp(−εσ/12) ≤ n−(c+8) , (23) where the last inequality follows from Condition (20) and the choice Cε = 100/ε. Let ESafe be the event that, in every one of the first T0 iterations and for every open color i, the number of proposals to i is at most its remaining budget Bi . We now apply the union bound to the estimate of Eq. (23) over all colors and all iterations. In the calls made by Algorithm 7, the number of colors is at most 2(∆ + 1) ≤ 2n. Also, since σ ≤ n, Condition (20) implies ε−1 ≤ n/6 and ε−1 (c + 6) lg n ≤ n/100. Consequently, T0 = ⌈64ε−2 (c + 4) lg n⌉ ≤ n2 for n ≥ 2. Hence P[ESafe ] ≤ 2n · n2 · n−(c+8) ≤ n−(c+4) . Next, to prove progress, we bound the probability that an uncolored vertex v becomes a conflictfree candidate in a given iteration. Fix a vertex v that is still uncolored at the beginning of some iteration t ≤ T0 , and condition on the history up to that iteration. By Lemma 8.3, v has at least dtunc (v) + 1 open locally valid colors. If v becomes active, it chooses one of these colors uniformly. For any uncolored neighbor u of v, the probability that u proposes the same color as v is at most p0 /χtopen (v). Taking a union bound over the dtunc (v) uncolored neighbors of v, the probability that some such neighbor proposes the same color is at most p0 χtopen (v)

· dtunc (v) ≤

dtunc (v) · p0 ≤ p0 . dtunc (v) + 1

30

Therefore, in every iteration t in which v is still uncolored, the probability of the event Esuccess (v, t) that v becomes a conflict-free candidate satisfies P[Esuccess (v, t)] ≥ p0 (1 − p0 ) ≥ p0 /2.

(24)

On the event ESafe , every conflict-free candidate is accepted: indeed, for each color i, the total number of proposals to i is at most Bi , so the number of candidates for i is also at most Bi , and the quota step admits all of them. Hence, if ESafe holds and a vertex v ever becomes a conflict-free candidate during the first T0 iterations, then v is colored. T 0 It remains to bound the probability of the event Enever (v) ≡ Tt=1 Ēsuccess (v, t)] that the vertex v never becomes a conflict-free candidate. The lower bound of Eq. (24) holds conditionally on every history in which the vertex is still uncolored, so by multiplying the conditional failure probabilities, P[Enever (v)] ≤ (1 − p0 /2)T0 ≤ exp(−p0 T0 /2) ≤ n−2(c+4) . Taking a union bound over all vertices gives probability at most n · n−2(c+4) ≤ n−(c+3) that some vertex remains uncolored after T0 iterations while ESafe holds. Combining this with P[ESafe ] ≤ n−(c+4) , the total failure probability is at most n−(c+2) for n ≥ 2. Thus, with probability at least 1 − n−(c+2) , Algorithm Budget Recolor terminates within T0 = O(ε−2 (c + 4) lg n) iterations. By Lemma 8.1, the returned coloring is valid and every target color receives at most fph max new vertices. Lemma 8.5. Let f′max = σ +⌈lg(∆+1)⌉⌈(1+ε)σ⌉. Suppose that after the while loop of Algorithm 7 (LogCap Compact), the current coloring is valid, has ∆ + 2 colors, and every color has frequency in [σ/2, f′max ]. Then the final cleanup step of Algorithm 7, if its call to Recolor succeeds, returns a valid coloring with ∆ + 1 colors and frequency range [σ/2, f′max + σ]. Proof. After the while loop terminates, Algorithm 7 keeps the ∆ + 1 most frequent colors as Ptarget and cancels the least frequent color, iχ , where χ = ∆ + 2. The set of canceled vertices is Vtarget = V (iχ ). Since the frequency of the least frequent color is at most the average frequency, |Vtarget | ≤

n n < = σ. ∆+2 ∆+1

The target palette has size ∆ + 1, so Lemma 2.3 applies to the partial coloring obtained after canceling Vtarget . Hence the call to Recolor(Vtarget , Ptarget ) returns a valid coloring using only colors of Ptarget . Therefore the final palette size is at most ∆ + 1. Turning to the resulting frequencies, every color in Ptarget already existed before the cleanup and had frequency at least σ/2; during the cleanup it could only gain vertices. Hence it still preserves the lower frequency threshold σ/2. The coloring before the cleanup obeyed the upper frequency threshold f′max . During the cleanup, any fixed target color can gain at most all vertices of Vtarget , and |Vtarget | ≤ σ. Therefore the output colors obey the upper frequency threshold f′max + σ = 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉. The lemma follows. For the sake of the time analysis of Section 9 we note the following:

31

Fact 8.6. Algorithm LogCap Compact begins with one call to Iter NBC. The excess palette size drops by a factor of two in each phase, so the algorithm has O(lg ∆) phases. Lemma 8.4 gives O(ε−2 (c + 4) lg n) iterations of Budget Recolor per phase. Each such iteration uses CA for counters and open-color information, and QA for quota admission. Then, the algorithm calls once to Recolor. When c, ε are fixed admissible constants, ε−2 (c + 4) = Ω(1) and this factor disappears. Theorem 8.7. For constants c and ε satisfying Conditions (20), Algorithm 7 (LogCap Compact) computes, with probability at least 1 − n−c , a valid coloring with at most ∆ + 1 colors and frequency range [σ/2, 2σ + ⌈lg(∆ + 1)⌉⌈(1 + ε)σ⌉]. Its running times are T seq (LogCap Compact) = O(m lg n lg ∆), T cngst (LogCap Compact) = O((D+∆) lg n lg ∆) and T cc (LogCap Compact) = O(lg n lg ∆). Every output color i satisfies Proof. The lower bound is preserved throughout the algorithm. The initialization by Iter NBC gives f(i) ≥ σ/2 for every color. Thereafter, colors are either removed or gain vertices; no new color is created. Consider one phase, and let χremove = ⌊χexcess /2⌋. The target palette size is χtarget = χ − χremove = ∆ + 1 + s,

s = χexcess − χremove = ⌈χexcess /2⌉.

By Lemma 8.2, |Vtarget | ≤ χremove · σ ≤ sσ. Therefore Lemma 8.4 applies to the call to Algorithm 8 (Budget Recolor) in this phase. During the phase, each target color receives at most ⌈(1 + ε)σ⌉ new vertices. The excess satisfies new χexcess = χexcess − ⌊χexcess /2⌋ = ⌈χexcess /2⌉.

Since initially χexcess ≤ ∆ + 1, after at most ⌈lg(∆ + 1)⌉ phases the excess is at most 1, which is equivalent to χ ≤ ∆ + 2. A surviving color starts with frequency at most σ after Iter NBC and can gain at most ⌈(1+ε)σ⌉ vertices in each phase. This gives the stated upper bound f′max . Then, combined with Lemma 8.5, we get our needed results. Finally, use the standard high-probability guarantee of Iter NBC with failure probability at most n−(c+1) , and use Lemma 8.4 for the recoloring phases, in addition to the standard high-probability guarantee of Recolor. Each recoloring phase fails with probability at most n−(c+2) . There are at most ⌈lg(∆ + 1)⌉ ≤ lg n + 1 ≤ n such phases for n ≥ 2, so the total recoloring failure probability is at most n−(c+1) . A union bound over the initialization and all recoloring phases gives failure probability at most 2n−(c+1) ≤ n−c , as claimed. The runtime statement follows from Fact 8.6 and is calculated in Section 9.

9

Implementation Details and Runtimes

This section supplies the model-dependent costs for the primitives of Section 2 and then substitutes them into the local runtime facts appearing in the algorithmic sections. Costs in the sequential model: As mentioned earlier, the modular description of our algorithms using basic primitives does not exactly fit the sequential implementation. For example, in the distributed implementations, before 32

invoking LC, the vertices must learn the globally chosen target palette, or equivalently the targetlist information induced by that palette; we charge this preparation as a CA-type operation. In the sequential implementation this bookkeeping need not be performed as a separate primitive: the algorithm stores the current color classes and can form the admissible lists while scanning the graph for the sequential LC simulation. This distinction does not affect any of our asymptotic bounds, since both the sequential bookkeeping and the sequential LC simulation cost O(m). Thus, even when a higher-level algorithm invokes Recolor repeatedly, charging each activation schematically as target-list preparation plus one LC call gives the same sequential running time up to constant factors. Let us now discuss the sequential implementation of our algorithms in more detail. The graph is stored by adjacency lists together with the current color-class lists. The LC primitive is implemented directly on these lists. For each target vertex, the algorithm marks the colors already used by its colored neighbors, scans the implicit admissible palette until it finds an unmarked color, assigns that color, and then clears the temporary marks. Equivalently, this is the standard sequential simulation of list coloring when the lists are represented by a global palette together with locally forbidden neighbor colors. Each edge incident to the target set is inspected only a constant number of times, so the LC call costs O(m) in our notation. CA is implemented by a linear scan that increments per-color counters, maintains the requested per-color records, and bucket-sorts colors when an order by frequency is needed. QA is implemented by scanning the candidate lists for the participating colors, keeping the best ranked or first feasible candidates up to the prescribed quota. Hence T seq (LC) = T seq (CA) = T seq (QA) = O(m). Here CA recomputes or bucket-sorts color records in linear time, and QA scans candidate lists. Thus T seq (Color All) = T seq (Recolor) = T seq (Split) = O(m). Costs in the CONGEST model: The global coordination primitives are routed on a BFS tree. A CA call sends one O(lg n)-bit record per relevant color through a pipelined convergecast, aggregates the counts or other per-color statistics at the root, and broadcasts the resulting color records back to the vertices. Since all palettes used by the algorithms have size O(∆) after the initial coloring stage, the pipeline cost is O(D + ∆). A QA call is similar: candidate vertices send color-indexed requests or ranks, the coordinator/root admits at most the requested quota for each color, and the decisions are pipelined back down the tree, again using O(∆) color records. For LC, once the local lists are known, we use the randomized CONGEST list-coloring algorithm of Halldorsson, Nolin, and Tonoyan [6], getting T cngst (LC) = O(lg5 lg n). For the global primitives we get T cngst (CA) = T cngst (QA) = O(D + ∆). In the Congested Clique, every pair of vertices can exchange an O(lg n)-bit message in one round, and standard routing lets the color-indexed records used by CA and QA be delivered to their coordinators in constant rounds. Each color can be assigned a coordinator, which receives the relevant frequency counts, candidate ranks, or quota requests, makes the deterministic admission/counting decision locally, and sends the answer back to the affected vertices. The LC primitive is constant-round by the Congested Clique coloring algorithms of Czumaj, Davies, and Parter [2, 3]. Therefore T cc (LC) = T cc (CA) = T cc (QA) = O(1). The named procedures are then charged through these primitives. Color All and Recolor are LC calls, with the relevant target lists prepared by the surrounding CA step when needed. Split is charged as CA plus QA, not as a separate primitive: CA identifies the colors above the threshold and computes their descendant quotas, while QA assigns the vertices of each such color to final descendant colors. Algorithm calculations. Substituting the primitive costs stated above into Facts 3.4, 4.3, 5.3, 33

5.5, 6.3, 6.5, 7.6, and 8.6 gives the time bounds in our theorems and Table 1.

10

Future Directions

In this work, we presented a suite of algorithms for near-equitable coloring and discussed their implementation in the CC, congest and sequential models. Several promising avenues for future research arise from our results and the limitations of the current approach. Optimized Recoloring Strategies. The core of our iterative algorithms relies on Procedure Recolor, where low frequency color are dissolved and the uncolored vertices select new colors uniformly at random from their available palette. This method may not be optimal for convergence speed or load balancing. A potential improvement would be to introduce non-uniform probability distributions. For instance, a vertex could choose a target color cj with a probability inversely proportional to |V (j)|, thereby naturally biasing the process towards filling smaller under-capacity classes first. Additionally, rather than attempting to recolor with probability 1 (which causes high contention), vertices could retain their current color with a certain probability, or attempt to switch only if local contention is below a threshold. Exploring these weighted or probabilistic heuristics could yield faster convergence rates or tighter bounds on the frequency range. Topology-Specific Optimizations. While our results apply to general graphs, many distributed systems operate on specific topologies such as rings, trees, or grids. It is well known that for rings and trees, a 3-coloring can be computed in O(lg∗ n) rounds in the LOCAL model. An interesting question is whether equitable coloring can be achieved with similar efficiency on special graph classes. Specifically, can we achieve a near-equitable coloring on a ring or tree in O(lg∗ n) rounds, or does the global balance constraint impose a strictly higher lower bound on the runtime, regardless of the local topology? Optimal deterministic solution in CC A natural and plausible direction is to exploit the powerful techniques of Czumaj, Davies, and Parter [2, 3] in order to derive a deterministic constant-round algorithm for near-equitable coloring in the CC model, that for any constant parameters ρ, η ∈ (0, 1) computes a valid coloring ϕ : V → P with palette size χ ≤ (1 + ρ)(∆ + 1) and frequency range [max{1, ⌊(1−η)σ⌋}, ⌈(1+η)σ⌉]. Such an algorithm would require adapting the recursive partitioning technique, parallel seed-fixing machinery and bounded-independence concentration framework of [2, 3] and proving the balanced split estimates directly. To achieve near-equitable frequencies rather than arbitrary list colorings, it may be necessary to replace their palette invariants with a strict two-sided bin-size condition. Palettes can be exclusively established at the leaves of the recursion, and vertices experiencing unfavorable hash distributions would have to be postponed and absorbed bottom-up subject to strict capacity limits. We are currently working on making these ideas rigorous and writing up the resulting algorithm and analysis. Note that it appears that the resulting coloring will require (1 + ρ)(∆ + 1) colors. A more challenging goal would be to derive a fast algorithm of this type that uses ∆ + o(∆) colors, or even a fast algorithm comparable to Algorithm LogCap Compact of Section 8, which uses ∆ + 1 colors. Another challenge is to find a viable way to extend this approach to the CONGEST or sequential models.

34

References [1] B. S. Baker and J. Coffman, Edward G. Mutual exclusion scheduling. Theoretical Computer Science, 162(2):225–243, 1996. [2] A. Czumaj, P. Davies, and M. Parter. Simple, deterministic, constant-round coloring in the congested clique. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 310–318, 2020. [3] A. Czumaj, P. Davies, and M. Parter. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing, 50(5):1603–1626, 2021. [4] D. de Werra. An introduction to timetabling. European Journal of Operational Research, 19(2):151–162, 1985. [5] A. Hajnal and E. Szemerédi. Proof of a conjecture of P. erdős. In P. Erdős, A. Rényi, and V. T. Sós, editors, Combinatorial Theory and Its Applications, Vol. II, pages 601–623. NorthHolland, Amsterdam, 1970. [6] M. M. Halldórsson, A. Nolin, and T. Tonoyan. Overcoming congestion in distributed coloring. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 26–36. Association for Computing Machinery, 2022. [7] Ö. Johansson. Simple distributed δ + 1-coloring of graphs. Information Processing Letters, 70:229––232, 1999. [8] H. A. Kierstead, A. V. Kostochka, M. Mydlarz, and E. Szemerédi. A fast algorithm for equitable coloring. Combinatorica, 30(2):217–224, 2010. [9] Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg. MST construction in O(log log n) communication rounds. In Proc. 15th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 94—-100, 2003. [10] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. [11] D. C. Wood. A technique for colouring a graph applicable to large scale timetabling problems. The Computer Journal, 12(4):317–319, 1969.

35

Related documents

• Greedy-Like Defective Coloring: Distributed Algorithms and Applications#423920
• Greedy-Like Defective Coloring: Distributed Algorithms and Applications#999838
• Algorithmic fairness in mortgage lending: from absolute conditions to relational trade-offs#747710
• Algorithmic Fairness in Computational Medicine#679223
• On the Parameterized Complexity of Coloring Discovery#996655