pith. sign in

arxiv: 2405.04648 · v1 · submitted 2024-05-07 · 💻 cs.DS · cs.DC· cs.DM

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms

Marc Fuchs , Fabian Kuhn This is my paper

Pith reviewed 2026-05-24 00:57 UTC · model grok-4.3

classification 💻 cs.DS cs.DCcs.DM
keywords distributed coloringlist defective coloringCONGEST modeldefective coloringneighborhood independenceedge orientationgraph algorithms
0
0 comments X

The pith

Two sweeps over an oriented graph solve list defective coloring when lists have size p² and satisfy a defect sum condition.

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

The paper develops list variants of simple iterative defective coloring algorithms. It shows that when every node has a color list of size p squared and the sum over each list of (allowed defect plus one) exceeds p times the maximum outdegree β in some edge orientation, two sweeps over the nodes suffice to assign each node a color meeting its outneighbor defect bound. This produces simpler and computationally lighter algorithms than prior list defective coloring work. The result directly yields an alternative distributed algorithm for (Δ+1)-coloring that runs in Õ(√Δ) plus O(log* n) rounds in the CONGEST model and extends to recursive coloring on graphs with bounded neighborhood independence.

Core claim

If all nodes have lists of size p² and ∀v: ∑_{x∈L_v}(d_v(x)+1) > p·β, then two sweeps of the nodes in opposite order over an edge-oriented graph with maximum outdegree β let each node v choose a color x∈L_v such that at most d_v(x) outneighbors of v receive color x. This generalizes known defective coloring results and supplies new distributed algorithms for standard coloring problems.

What carries the argument

The two-sweep procedure on an edge-oriented graph that assigns colors from lists to meet per-color outneighbor defect bounds under the p² list-size and defect-sum conditions.

If this is right

  • Yields an alternative Õ(√Δ) + O(log* n)-round algorithm for (Δ+1)-coloring in the CONGEST model.
  • Extends the single-sweep defective coloring approach to the list setting for graphs of neighborhood independence θ.
  • Produces a (log Δ)^{O(log log Δ)} + O(log* n)-round algorithm when θ is constant.
  • Supplies list defective coloring that is simpler and computationally faster than previous methods.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The two-sweep method might combine with other orientation strategies to improve round complexity in additional models.
  • List defective coloring could serve as a building block for distributed solutions to further sparse graph problems.
  • The simplicity of the sweeps may allow direct implementation without heavy preprocessing in restricted communication settings.

Load-bearing premise

The graph admits an edge orientation with maximum outdegree β and the lists satisfy the size p² and per-node defect-sum conditions.

What would settle it

A concrete graph, orientation of outdegree β, and lists of size p² with all defect sums > p β such that after two sweeps at least one node exceeds its allowed defect for the chosen color.

Figures

Figures reproduced from arXiv: 2405.04648 by Fabian Kuhn, Marc Fuchs.

Figure 1
Figure 1. Figure 1: The picture illustrates a node v (in red) together with its outneighbors in N<(v) (in blue) and N>(v) (in green). Note that when node v has to pick the set Sv in Phase I, all blue nodes u have already picked their subset Su of their color list and have sent it to v. In Phase II, v has to output a final color from Sv. At this point, the green nodes (N<(v)) have already picked their final colors. Node v ther… view at source ↗
read the original abstract

In this paper, we give list coloring variants of simple iterative defective coloring algorithms. Formally, in a list defective coloring instance, each node $v$ of a graph is given a list $L_v$ of colors and a list of allowed defects $d_v(x)$ for the colors. Each node $v$ needs to be colored with a color $x\in L_v$ such that at most $d_v(x)$ neighbors of $v$ also pick the same color $x$. For a defect parameter $d$, it is known that by making two sweeps in opposite order over the nodes of an edge-oriented graph with maximum outdegree $\beta$, one can compute a coloring with $O(\beta^2/d^2)$ colors such that every node has at most $d$ outneighbors of the same color. We generalize this and show that if all nodes have lists of size $p^2$ and $\forall v:\sum_{x\in L_v}(d_v(x)+1)>p\cdot\beta$, we can make two sweeps of the nodes such that at the end, each node $v$ has chosen a color $x\in L_v$ for which at most $d_v(x)$ outneighbors of $v$ are colored with color $x$. Our algorithm is simpler and computationally significantly more efficient than existing algorithms for similar list defective coloring problems. We show that the above result can in particular be used to obtain an alternative $\tilde{O}(\sqrt{\Delta})+O(\log^* n)$-round algorithm for the $(\Delta+1)$-coloring problem in the CONGEST model. The neighborhood independence $\theta$ of a graph is the maximum number of pairwise non-adjacent neighbors of some node of the graph. It is known that by doing a single sweep over the nodes of a graph of neighborhood independence $\theta$, one can compute a $d$-defective coloring with $O(\theta\cdot \Delta/d)$ colors. We extend this approach to the list defective coloring setting and use it to obtain an efficient recursive coloring algorithm for graphs of neighborhood independence $\theta$. In particular, if $\theta=O(1)$, we get an $(\log\Delta)^{O(\log\log\Delta)}+O(\log^* n)$-round algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper gives list-defective variants of known iterative defective-coloring procedures. The central result states that, given an orientation of maximum out-degree β together with per-node lists L_v of size p² satisfying ∑_{x∈L_v}(d_v(x)+1) > p·β for every v, two sweeps (in opposite order) produce a coloring in which each v selects x∈L_v with at most d_v(x) out-neighbors also colored x. The same technique is extended to a single-sweep list-defective procedure on graphs of neighborhood independence θ. These primitives are used to obtain an alternative Õ(√Δ)+O(log* n)-round (Δ+1)-coloring algorithm in CONGEST and a (log Δ)^{O(log log Δ)}+O(log* n)-round algorithm when θ=O(1).

Significance. If the stated conditions hold, the work supplies a simpler, parameter-light constructive procedure for list defective coloring that directly yields known round-complexity bounds for (Δ+1)-coloring and improves the state of the art for bounded-neighborhood-independence graphs. The arithmetic contradiction argument (if every color violated its defect bound then the sum of counts would exceed both the list-size and out-degree bounds) is a clear strength; the absence of fitted parameters or self-referential definitions makes the result easy to apply as a black-box primitive.

minor comments (2)
  1. The manuscript should explicitly state whether the required edge orientation of out-degree ≤β is assumed to be given as part of the input or must be computed inside the CONGEST algorithm; a one-sentence clarification in §3 would remove ambiguity for implementers.
  2. Notation for the two opposite-order sweeps is introduced only in the abstract; adding a short pseudocode block or a numbered paragraph in the main body would make the reduction from the non-list case to the list case easier to follow.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation to accept. The review accurately captures the contributions of our list-defective coloring primitives and their applications to CONGEST coloring.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's core result is a direct constructive generalization of the two-sweep out-defective coloring procedure to the list-defective setting. The key existence argument at each node is a self-contained counting contradiction: if every color x satisfied count_x >= d_v(x)+1 then sum count_x >= sum(d_v(x)+1) > p beta, contradicting the out-degree bound beta. This arithmetic holds independently of processing order and does not rely on fitted parameters, self-referential definitions, or load-bearing self-citations. The neighborhood-independence extension follows from an analogous single-sweep counting argument. The derivation is therefore self-contained against the stated premises.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic assumptions (existence of bounded-outdegree orientations, basic properties of lists and defects) with no fitted numerical parameters and no newly postulated entities.

axioms (2)
  • standard math Every graph admits an orientation with maximum outdegree equal to its maximum degree
    Invoked implicitly when the two-sweep procedure is applied to an edge-oriented graph with outdegree β.
  • domain assumption The list-size and defect-sum conditions are supplied as input
    The algorithm's guarantee is conditional on these per-node list properties being satisfied.

pith-pipeline@v0.9.0 · 5958 in / 1311 out tokens · 34873 ms · 2026-05-24T00:57:58.950442+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    A fast and simple randomized parallel algorithm for the maximal independent set problem

    Noga Alon, L \' a szl \' o Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem . Journal of Algorithms , 7(4):567--583, 1986

    work page 1986

  2. [2]

    Goldberg, Michael Luby, and Serge A

    Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In Proc.\ 30th Symp.\ on Foundations of Computer Science (FOCS) , pages 364--369, 1989

    work page 1989

  3. [3]

    Deterministic ( +1 )-coloring in sublinear (in ) time in static, dynamic, and faulty networks

    Leonid Barenboim. Deterministic ( +1 )-coloring in sublinear (in ) time in static, dynamic, and faulty networks. Journal of ACM , 63(5):1--22, 2016

    work page 2016

  4. [4]

    Distributed edge coloring in time polylogarithmic in

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time polylogarithmic in . In Proc.\ 41st ACM Symp.\ on Principles of Distributed Computing (PODC) , pages 15--25, 2022

    work page 2022

  5. [5]

    Distributed (delta+1)-coloring in linear (in delta) time

    Leonid Barenboim and Michael Elkin. Distributed (delta+1)-coloring in linear (in delta) time. In Proc.\ 41st Annual ACM Symp.\ on Theory of Computing (STOC) , pages 111--120, 2009

    work page 2009

  6. [6]

    Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

    Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Comput. , 22:363--379, 2010

    work page 2010

  7. [7]

    Distributed deterministic edge coloring using bounded neighborhood independence

    Leonid Barenboim and Michael Elkin. Distributed deterministic edge coloring using bounded neighborhood independence. In Proc.\ 30th ACM Symp.\ on Principles of Distributed Computing (PODC) , pages 129--138, 2011

    work page 2011

  8. [8]

    Locally-iterative distributed ( +1) -coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models

    Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed ( +1) -coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proc.\ 37th ACM Symp.\ on Principles of Distributed Computing (PODC) , pages 437--446, 2018

    work page 2018

  9. [9]

    The Locality of Distributed Symmetry Breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Distributed Symmetry Breaking . Journal of the ACM , 63(3):1--45, 2016

    work page 2016

  10. [10]

    A lower bound for the distributed lov \' a sz local lemma

    Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi \" a inen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lov \' a sz local lemma. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016...

    work page 2016

  11. [11]

    Locality of not-so-weak coloring

    Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela. Locality of not-so-weak coloring. In Proc.\ 26th Int.\ Coll.\ on Structural Information and Communication Complexity (SIROCCO) , pages 37--51, 2019

    work page 2019

  12. [12]

    Distributed edge coloring in time quasi-polylogarithmic in delta

    Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time quasi-polylogarithmic in delta. In Proc.\ 39th ACM Symp.\ on Principles of Distributed Computing (PODC) , pages 289--298, 2020

    work page 2020

  13. [13]

    An exponential separation between randomized and deterministic complexity in the LOCAL model

    Yi - Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM Journal on Computing , 48(1):122--143, 2019

    work page 2019

  14. [14]

    An optimal distributed ( \( \) +1)-coloring algorithm? In Proc.\ 50th ACM Symp.\ on Theory of Computing, (STOC) , pages 445--456, 2018

    Yi - Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed ( \( \) +1)-coloring algorithm? In Proc.\ 50th ACM Symp.\ on Theory of Computing, (STOC) , pages 445--456, 2018

    work page 2018

  15. [15]

    Distributed algorithms for the Lov \' a sz local lemma and graph coloring

    Kai - Min Chung, Seth Pettie, and Hsin - Hao Su. Distributed algorithms for the Lov \' a sz local lemma and graph coloring. Distributed Computing , 30(4):261--280, 2017

    work page 2017

  16. [16]

    Cole and U

    R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control , 70(1):32--53, 1986

    work page 1986

  17. [17]

    Sublogarithmic distributed algorithms for lov \' a sz local lemma, and the complexity hierarchy

    Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for lov \' a sz local lemma, and the complexity hierarchy. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria , volume 91 of LIPIcs , pages 18:1--18:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2017

    work page 2017

  18. [18]

    Halld \' o rsson, Fabian Kuhn, and Alexandre Nolin

    Maxime Flin, Mohsen Ghaffari, Magn \' u s M. Halld \' o rsson, Fabian Kuhn, and Alexandre Nolin. Coloring fast with broadcasts. In Proc.\ 35th ACM Symp.\ on Parallelism in Algorithms and Architectures (SPAA) , pages 455--465, 2023

    work page 2023

  19. [19]

    Deterministic distributed edge-coloring via hypergraph maximal matching

    Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In Proc.\ 58th IEEE Symp.\ on Foundations of Computer Science (FOCS) , pages 180--191, 2017

    work page 2017

  20. [20]

    Local conflict coloring

    Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Proc.\ 57th IEEE Symp.\ on Foundations of Computer Science (FOCS) , pages 625--634, 2016

    work page 2016

  21. [21]

    List Defective Colorings: Distributed Algorithms and Applications

    Marc Fuchs and Fabian Kuhn. List Defective Colorings: Distributed Algorithms and Applications . In 37th International Symposium on Distributed Computing (DISC 2023) , volume 281 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 22:1--22:23, 2023

    work page 2023

  22. [22]

    List defective colorings: Distributed algorithms and applications

    Marc Fuchs and Fabian Kuhn. List defective colorings: Distributed algorithms and applications. CoRR , abs/2304.09666, 2023

    work page arXiv 2023

  23. [23]

    Faster deterministic distributed MIS and approximate matching

    Mohsen Ghaffari and Christoph Grunau. Faster deterministic distributed MIS and approximate matching. In Proc.\ 55th ACM Symp.\ on Theory of Computing (STOC) , pages 1777--1790, 2023

    work page 2023

  24. [24]

    Improved deterministic network decomposition

    Mohsen Ghaffari, Christoph Grunau, and V \' a clav Rozhon. Improved deterministic network decomposition. In Proc.\ 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2904--2923, 2021

    work page 2021

  25. [25]

    Harris, and Fabian Kuhn

    Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 , pages 662--673. IEEE Computer Society, 2018

    work page 2018

  26. [26]

    Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition

    Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proc.\ 62nd IEEE Symp.\ on Foundations of Computing (FOCS) , 2021

    work page 2021

  27. [27]

    Goldberg, S.A

    A.V. Goldberg, S.A. Plotkin, and G.E. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics , 1(4):434--446, 1988

    work page 1988

  28. [28]

    Halld \' o rsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan

    Magn \' u s M. Halld \' o rsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. Efficient randomized distributed coloring in CONGEST . In Proc.\ 53rd ACM Symp.\ on Theory of Computing (STOC) , pages 1180--1193, 2021

    work page 2021

  29. [29]

    Halld \' o rsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan

    Magn \' u s M. Halld \' o rsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. Near-optimal distributed degree+1 coloring. In Proc.\ 54th ACM Symp.\ on Theory of Computing (STOC) , pages 450--463, 2022

    work page 2022

  30. [30]

    Halld \' o rsson, Alexandre Nolin, and Tigran Tonoyan

    Magn \' u s M. Halld \' o rsson, Alexandre Nolin, and Tigran Tonoyan. Overcoming congestion in distributed coloring. In Proc.\ 42nd Symp.\ on Principles of Distributed Computing (PODC) , pages 26--36, 2022

    work page 2022

  31. [31]

    Harris, Johannes Schneider, and Hsin - Hao Su

    David G. Harris, Johannes Schneider, and Hsin - Hao Su. Distributed ( \( \) +1)-coloring in sublogarithmic rounds. J. ACM , 65(4):19:1--19:21, 2018

    work page 2018

  32. [32]

    Adapting local sequential algorithms to the distributed setting

    Ken - ichi Kawarabayashi and Gregory Schwartzman. Adapting local sequential algorithms to the distributed setting. In Proc.\ 32nd Symp.\ on Distributed Computing (DISC) , pages 35:1--35:17, 2018

    work page 2018

  33. [33]

    Local weak coloring algorithms and implications on deterministic symmetry breaking

    Fabian Kuhn. Local weak coloring algorithms and implications on deterministic symmetry breaking. In Proc.\ 21st ACM Symp.\ on Parallelism in Algorithms and Architectures (SPAA) , 2009

    work page 2009

  34. [34]

    Faster deterministic distributed coloring through recursive list coloring

    Fabian Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Proc.\ 32st ACM-SIAM Symp.\ on Discrete Algorithms (SODA) , pages 1244--1259, 2020

    work page 2020

  35. [35]

    On the complexity of distributed graph coloring

    Fabian Kuhn and Roger Wattenhofer. On the complexity of distributed graph coloring. In Proc.\ 25th ACM Symp.\ on Principles of Distributed Computing (PODC) , pages 7--15, 2006

    work page 2006

  36. [36]

    Distributive graph algorithms – Global solutions from local data

    Nathan Linial. Distributive graph algorithms – Global solutions from local data . In Proc.\ 28th Symp.\ on Foundations of Computer Science (FOCS) , pages 331--335. IEEE, 1987

    work page 1987

  37. [37]

    Lov\'asz

    L. Lov\'asz. On decompositions of graphs. Studia Sci. Math. Hungar. , 1:237--238, 1966

    work page 1966

  38. [38]

    A simple parallel algorithm for the maximal independent set problem

    Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing , 15(4):1036--1053, 1986

    work page 1986

  39. [39]

    Local conflict coloring revisited: Linial for lists

    Yannic Maus and Tigran Tonoyan. Local conflict coloring revisited: Linial for lists. In Proc.\ 34th Symp.\ on Distributed Computing (DISC) , volume 179 of LIPIcs , pages 16:1--16:18, 2020

    work page 2020

  40. [40]

    Distributed Computing: A Locality-Sensitive Approach

    David Peleg. Distributed Computing: A Locality-Sensitive Approach . Society for Industrial and Applied Mathematics, USA, 2000

    work page 2000

  41. [41]

    On the complexity of distributed network decomposition

    Alessandro Panconesi and Aravind Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms , 20(2):356--374, 1996

    work page 1996

  42. [42]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization

    V \' a clav Rozho n and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc.\ 52nd ACM Symp.\ on Theory of Computing (STOC) , pages 350--363, 2020

    work page 2020