Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

Round and Communication Efficient Graph Coloring

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that (Δ+1)-vertex coloring and (2Δ−1)-edge coloring can both be solved in the two-party communication model with O(n) bits, the first with O(log log n · log Δ) rounds and the second with O(1) rounds, and that the…

desk verdict Strong edge coloring results, but the vertex coloring proof has a localized Chernoff gap that needs fixing before Theorem 1 is fully established. read the letter →

arxiv 2412.12589 v2 pith:U2HNSAAV submitted 2024-12-17 cs.DS cs.DC

Yi-Jun Chang , Gopinath Mishra , Hung Thuan Nguyen , Farrel D Salim This is my paper · ORCID
classification cs.DScs.DC MSC 05C1568Q1768R1068W2068W40
keywords graphcoloringcommunicationcomplexityvertexedgerandomcolortrialtwo-partyprotocolsW-streamingmodellowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Two players, Alice and Bob, each hold part of a graph's edges. This paper gives a randomized protocol that finds a proper (Δ+1)-vertex coloring of any n-vertex graph of maximum degree Δ using O(n) bits of communication in expectation and O(log log n · log Δ) rounds in the worst case, and a deterministic protocol that finds a (2Δ−1)-edge coloring using O(n) bits and O(1) rounds. It also proves an Ω(n)-bit lower bound for any randomized (2Δ−1)-edge coloring protocol with success probability at least 1/2. Together these results make both coloring problems communication-optimal and round-efficient in the two-party model, where the previous vertex-coloring protocol achieved the same bit bound only at the cost of O(n) expected rounds.

What carries the argument

The paper's vertex-coloring machine is the random color trial. In each iteration every active vertex is awake with probability 1/2 and uses the Color-Sample primitive to draw uniformly from its currently available colors; a vertex keeps its color only if no neighbor drew the same color, and the probability of staying active decays as (23/24)^i. The leftover instance is then handled by palette sparsification, which keeps O(log² Z) colors per vertex and leaves a sparse, still-colorable subproblem. For edge coloring the machine is a structural decomposition: deferring edges between vertices of degree at least Δ−1 produces a degree-2 subgraph; a Δ-perfect matching (whose existence follows from integrality of fractional matchings in bipartite graphs) covers all degree-Δ vertices; after these removals the remaining subgraph meets Fournier's independence condition and can be colored with Δ−1 colors locally. The lower-bound machine is a zero-communication game on a constant-size graph with Δ=2, where any no-communication strategy wins with probability at most 11024/11025, amplified to $2^{{−Ω(n)}}$ by parallel repetition.

What would settle it

Run Algorithm 1 many times on a graph with one center vertex of degree Δ and Δ leaves, tracking the center's number of active neighbors after each of the first O(log log Δ) iterations; the O(n)-bit vertex-coloring claim depends on the empirical frequency of dropping below Δ/$2^{{2i}}$ being at most 1/log³Δ.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the linear-bit boundary for graph coloring does not force sequential behavior. The vertex-coloring protocol runs O(log log n) rounds of a random color trial in which active vertices independently sample available colors and keep them unless a neighbor collides; the leftover uncolored vertices form a degree+1-list coloring instance that is finished by palette sparsification. The edge-coloring protocol is fully deterministic: each player locally defers a degree-2 set of edges, removes a matching covering all degree-Δ vertices, and then applies Fournier's condition to color the remaining subgraph, while matching and deferred edges are colored with one shared special color or the other player's palette. The lower bound for (2Δ−1)-edge coloring is built from a constant-size zero-communication game on seven vertices and parallel repetition, and it carries over to a linear space lower bound for W-streaming algorithms.

Load-bearing premise

The vertex-coloring protocol's linear communication budget rests on the assumption that a vertex with many neighbors keeps a substantial number of them still uncolored through the early random-color-trial iterations; the paper needs the rare failures of this event to cost at most about 1/log³Δ probability per vertex, and if failures are more common the expected communication per vertex can blow up from constant to log²Δ.

Editorial extensions

If this is right

  • The (Δ+1)-vertex coloring protocol reaches the same O(n) expected communication as the earlier sequential protocol while cutting worst-case rounds from O(n) to O(log log n · log Δ).
  • The deterministic (2Δ−1)-edge coloring protocol uses O(n) bits and O(1) rounds, so edge coloring is solved with both optimal communication and constant round count.
  • The Ω(n) lower bound matches the O(n) upper bound, making the edge-coloring protocol communication-optimal up to constants, even against randomized protocols with constant success probability.
  • Corollary 1.2 gives the first nontrivial space lower bound for (2Δ−1)-edge coloring in the W-streaming model: any constant-pass randomized algorithm needs Ω(n) bits of space in expectation.
  • Because (2Δ)-edge coloring needs zero communication (Theorem 3), the 2Δ−1 color budget in the lower bound is the smallest one for which the problem is genuinely hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A cheap check of the vertex-coloring analysis is to simulate the random color trial on a large star and count how often the center's active-neighbor count falls below Δ/2^{2i} in the first O(log log Δ) iterations; the protocol's O(n)-bit claim is false if that frequency is not O(1/log³Δ).
  • The constant-size game plus parallel-repetition template is not specific to 3-edge-coloring; it may yield Ω(n) communication lower bounds for other locally checkable labeling problems in the two-party model, such as maximal matching or sinkless orientation.
  • If a round-parallel available-color sampler could replace the binary-search-based Color-Sample, the vertex-coloring round bound would drop to O(log log n) with no change in the O(n) bit budget; the log Δ factor is an artifact of the sampling primitive.
  • The W-streaming lower bound says nothing yet about (Δ+1)-edge coloring, and adapting the ZEC-NEW construction to fewer colors would be a natural next step.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. This paper studies two-party communication protocols for graph coloring. It presents a randomized (Δ+1)-vertex-coloring protocol with O(n) expected bits and O(log log n · log Δ) worst-case rounds, improving on the O(n)-round protocol of Flin and Mittal; a deterministic (2Δ−1)-edge-coloring protocol with O(n) bits and O(1) rounds; and an Ω(n)-bit lower bound for randomized (2Δ−1)-edge coloring with constant success probability, yielding a W-streaming space lower bound. The vertex-coloring protocol runs random color trials to leave O(n/log^4 n) uncolored vertices in expectation and then solves the leftover (degree+1)-list-coloring instance via palette sparsification. The edge-coloring protocol combines Vizing/Fournier-type decomposition, deferred subgraphs, matchings, and palette sharing. The lower bound is proved through a zero-communication edge-coloring game and Raz's parallel repetition theorem.

Significance. If the vertex-coloring analysis is completed, the results are significant: they give optimal communication with exponentially improved round complexity for vertex coloring, and they provide the first non-trivial communication protocol and matching lower bound for (2Δ−1)-edge coloring, plus a new space lower bound in the W-streaming model. The paper builds on published tools—Flin and Mittal's color sampling, Halldórsson et al.'s palette sparsification, Vizing's and Fournier's theorems, and Raz's parallel repetition—rather than on its own claims, and the edge-coloring protocol includes a welcome deterministic O(1)-round improvement. The lower-bound construction via the ZEC game is elegant and appears sound.

major comments (1)
  1. [Section 4.3, Lemma 4.11] The Chernoff bound in Lemma 4.11 is applied to the wrong event. The proof lets X be the number of idle active neighbors and states that 'fewer than a quarter of the neighbors idle' is Pr[X ≤ (1−1/2)·Δ/2^{2i+1}] = Pr[X ≤ Δ/2^{2i+2}]. But if d denotes the actual number of active neighbors of a high-degree vertex, the bad event for becoming low-degree is X < d/4, and d/4 ≥ Δ/2^{2i+2}. The event X ≤ Δ/2^{2i+2} is strictly smaller than X < d/4 whenever d > Δ/2^{2i}, so an upper bound on the smaller event does not bound the larger event. Consequently the claimed bound e^{−Δ/2^{2i+4}} does not follow from the written argument, and since Lemma 4.12 and Lemma 4.8 depend on it, Theorem 1's O(n) expected communication is not established as written. The lemma is repairable by applying Chernoff to the actual d: with E[X]=d/2 and δ=1/2, Pr[X < d/4] ≤ e^{−d/16} ≤ e^{−Δ/2^{2i+4}}. The revision should state the correct event and this derivation explicitly.
minor comments (4)
  1. [Section 4.3, Lemma 4.11 / Lemma 4.12] The phrase 'becomes low-degree in the ith iteration' is ambiguous about whether the transition is from iteration i to i+1 or from i−1 to i; the proof should fix the indexing, because the threshold changes as Δ/2^{2i} with i.
  2. [Section 4.3, proof of Lemma 4.12] The displayed sum contains a typo: 'e^{−Δ/2^{2t+4}}' should use the same index as the summation, and the intermediate bound switches between 1/log^3 Δ and 1/log^4 Δ inconsistently; the final estimate is correct after fixing the exponents.
  3. [Appendix A, Algorithm 3] The output line says 'Any element from X∩Y', but the problem k-Slack-Int asks for an element of [m] \(X∪Y); this should be corrected.
  4. [Section 4.3, Lemma 4.6] Lemma 4.6 is stated as an inequality, but the displayed derivation actually gives an equality E[C_i] = Pr[A_i=1]·E[C_i|A_i=1]; this is a minor presentation issue.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivation rests on external results, and the flagged Lemma 4.11 issue is a correctness concern, not a circular reduction.

full rationale

All load-bearing ingredients are external to this paper: Lemma 3.1 inherits the k-Slack-Int protocol of Flin and Mittal [FM25]; Proposition 3.2 is the palette sparsification theorem of Halldórsson, Kuhn, Nolin, and Tonoyan [HKN+22]; the edge-coloring upper bound invokes Vizing [Viz64] and Fournier [Fou73]; and the lower bound uses Raz/Holenstein parallel repetition [Raz98; Hol09] together with Newman's public-randomness elimination argument [New91]. None of these are self-citations, and none are defined in terms of the target claims. The paper's own protocols are built from these ingredients and analyzed directly: the expected communication of Random-Color-Trial is bounded by Lemmas 4.5 through 4.8, and the leftover D1LC instance is handled by the sparsification theorem plus Lemma 3.3. There is no fitted parameter renamed as a prediction and no uniqueness assertion imported from the authors' prior work. The reviewer-flagged weakness in Lemma 4.11 is a potential gap in a Chernoff event-inclusion argument, not a circularity: the bad event for becoming low-degree is larger than the event whose probability is bounded, but the target bound is still derivable from the same Chernoff inequality applied to the actual degree d. A proof gap on a probabilistic estimate does not make the theorem equivalent to its input by construction. Accordingly, no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new free parameters fitted to data and no invented physical or mathematical entities. All assumptions are standard theorems and published results in graph theory, communication complexity, and distributed computing. The main reliance on external results is on Flin and Mittal's color-sampling subroutine and the palette sparsification theorem, both clearly cited and used as black boxes.

assumptions (7)
  • standard math Vizing's theorem: every simple graph has a proper edge coloring with at most Δ+1 colors.
    Used as background for edge coloring in Section 3.4 and Theorem 3.
  • standard math Fournier's theorem: if vertices of maximum degree form an independent set, the graph is Δ-edge-colorable.
    Relied upon in the edge coloring protocols (Sections 3.4, 5).
  • domain assumption Palette sparsification theorem for degree+1 list coloring (HKN+22).
    Used in Proposition 3.2 to reduce list sizes in the D1LC protocol.
  • standard math Raz-Holenstein parallel repetition theorem.
    Used in the lower bound proof (Lemma 6.4) to amplify the ZEC game.
  • standard math Newman's theorem on converting public randomness to private randomness.
    Invoked in Section 3.1 and Lemma 6.1 to obtain protocols without public randomness.
  • standard math Integrality of the fractional matching polytope in bipartite graphs.
    Used in Lemma 5.3 to guarantee existence of a Δ-perfect matching.
  • domain assumption Flin and Mittal's k-Slack-Int protocol and its communication/round bounds.
    The vertex coloring protocol relies on this subroutine for sampling available colors (Lemma 3.1 and Appendix A).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Round and Communication Efficient Graph Coloring." pith.science (2026). https://pith.science/paper/U2HNSAAV

@misc{pith2026241212589,
  author       = {Pith},
  title        = {Pith review of: Round and Communication Efficient Graph Coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U2HNSAAV}},
  note         = {Machine review of arXiv:2412.12589}
}
abstract

In the context of communication complexity, we explore protocols for graph coloring, focusing on the vertex and edge coloring problems in $n$-vertex graphs $G$ with a maximum degree $\Delta$. We consider a scenario where the edges of $G$ are partitioned between two players. Our first contribution is a randomized protocol that efficiently finds a $(\Delta + 1)$-vertex coloring of $G$, utilizing $O(n)$ bits of communication in expectation and completing in $O(\log \log n \cdot \log \Delta)$ rounds in the worst case. This advancement represents a significant improvement over the work of Flin and Mittal [Distributed Computing 2025], who achieved the same communication cost but required $O(n)$ rounds in expectation, thereby making a significant reduction in the round complexity. Our second contribution is a deterministic protocol to compute a $(2\Delta - 1)$-edge coloring of $G$, which maintains the same $O(n)$ bits of communication and uses only $O(1)$ rounds. We complement the result with a tight $\Omega(n)$-bit lower bound on the communication complexity of the $(2\Delta-1)$-edge coloring problem, while a similar $\Omega(n)$ lower bound for the $(\Delta+1)$-vertex coloring problem has been established by Flin and Mittal [Distributed Computing 2025]. Our result implies a space lower bound of $\Omega(n)$ bits for $(2\Delta - 1)$-edge coloring in the $W$-streaming model, which is the first non-trivial space lower bound for edge coloring in the $W$-streaming model.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Faster Dynamic $(\Delta+1)$-Coloring Against Adaptive Adversaries

    cs.DS 2025-04 conditional novelty 7.0 of 10

    A randomized dynamic algorithm maintains a proper (Δ+1)-coloring against adaptive adversaries in Õ(n^{2/3}) amortized update time, improving the prior Õ(n^{8/9}) bound.

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [3]

    Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication

    arXiv: 2103.07027. url: https://arxiv.org/abs/2103.07027. A vailable at https://arxiv.org/abs/2103.07027. [Lin92] Nathan Linial. Locality in distributed graph algor ithms. SIAM J. Comput. , 21(1),

    work page Pith review arXiv

  2. [1992]

    [MK17] Ali Mashreghi and Valerie King

    doi: 10.1137/0221015. [MK17] Ali Mashreghi and Valerie King. Time-communication trade-offs for minimum span- ning tree construction. In Proceedings of the 18th International Conference on Dis- tributed Computing and Networking, Hyderabad, India, Janu ary 5–7, 2017 , page 8. ACM, 2017. url: http://dl.acm.org/citation.cfm?id=3007775. [New91] Ilan Newman. Pri...

    work page arXiv

  3. [2021]

    [CFG+19] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uit to, and Yufan Zheng

    doi: 10.1137/20M1366502. [CFG+19] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uit to, and Yufan Zheng. The complexity of (∆ + 1) coloring in congested clique, massively parallel computa- tion, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC) , Toronto, ON, Canada, 2019. doi: ...

    arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.