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

Magn\'us M. Halld\'orsson; Maxime Flin

REVIEW 2 major objections 4 minor 12 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read A fully dynamic randomized algorithm maintains a proper $(\Delta+1)$-coloring of a graph against adaptive adversaries in $\widetilde{O}(n^{2/3})$ amortized update time.

desk verdict Strong new ideas, but the central invariant proof has a real gap: outlier recoloring can duplicate colors outside M_D and RecolorMatching leaves stale colors in M_D, so the n^{2/3} bound is not established as written. read the letter →

arxiv 2504.19729 v2 pith:ZO5O52D2 submitted 2025-04-28 cs.DS

Maxime Flin , Magnús M. Halldórsson This is my paper · ORCID

classification cs.DS

keywords dynamicgraphcoloring(Δ+1)-coloringadaptiveadversarysparser-denserdecompositionalmost-cliquerandomcolortrialsstealingamortizedupdatetime

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

The paper claims a fully dynamic randomized algorithm that keeps a proper $(\Delta+1)$-coloring of an $n$-vertex graph with maximum degree $\Delta$ under edge insertions and deletions, even when the update sequence can react to the algorithm's past output colors. Against such adaptive adversaries, the algorithm runs in $\widetilde{O}(n^{2/3})$ amortized update time with high probability, improving on the previous $\widetilde{O}(n^{8/9})$ bound. The key structural move is a sparser-denser decomposition whose dense clusters are analyzed by average external and anti degree rather than by a fixed $\varepsilon$ parameter, letting the algorithm recolor dense vertices cheaply through an inlier/outlier split. If the result holds, it matches a natural $n^{2/3}$ barrier for dynamic $(\Delta+1)$-coloring algorithms against adaptive adversaries.

What carries the argument

The load-bearing object is the $(\varepsilon,\zeta)$-sparser-denser decomposition, a refined version of the classic sparse-dense decomposition: vertices are split into sparse vertices ($\zeta$-sparse neighborhoods) and dense clusters that are $\varepsilon$-almost-cliques whose average external plus anti degree is $O(\zeta/\varepsilon^2)$. The algorithm maintains this decomposition in the background and uses it to drive recoloring—sparse vertices keep at least $\Omega(\zeta)$ available colors and are recolored by random color trials, inliers are recolored by a deterministic scan over their $O(\zeta)$ external and anti neighbors, and outliers are recolored by random trials that steal colors from inliers. Color stealing forms a chain—sparse steals from matched, matched from outliers, outliers from inliers—and the matching invariant keeps a sufficiently large colorful matching in each cluster.

What would settle it

Run the algorithm on an adversarial update sequence engineered to keep a dense cluster at the boundary $a_D + e_D = O(\zeta/\varepsilon^2)$ and measure, after every update, whether the color-class bound $|\Phi[\chi]\cap S| \le O(n/\zeta + \log n)$ and the matching invariant hold. A single phase in which one of these fails, or in which an inlier finds no available clique-palette color, would give a concrete counterexample to the claimed $\widetilde{O}(n^{2/3})$ bound.

Watch

Extended reading notes

Core claim

The central discovery is that maintaining a dynamic $(\Delta+1)$-coloring against an adaptive adversary can be reduced to keeping a four-layer structural decomposition updated cheaply: sparser vertices, dense-cluster inliers, dense-cluster outliers, and matched pairs inside clusters. The algorithm recomputes a fresh coloring at the start of each phase of length $\Theta(n^{2/3})$, guaranteeing large color palettes for sparse vertices and a colorful matching of repeated colors in every dense cluster; during the phase, sparse vertices use random color trials and steal colors from denser neighbors, inliers are recolored deterministically from small external/anti-neighbor sets, and outliers are recolored by random trials that may steal an inlier's color. The amortized bound emerges from balancing the phase length, the $O(n/\zeta)$ color-class sizes, and the decomposition-maintenance cost with $\zeta = n^{2/3}$.

Load-bearing premise

The load-bearing premise is that the almost-clique decomposition of the graph can be maintained dynamically in $O(\eta^{-4}\log n)$ amortized time per update even against an adaptive adversary; if that black-box result fails, the runtime and correctness of the new algorithm no longer follow.

Editorial extensions

If this is right

If the theorem is correct, the update time for dynamic $(\Delta+1)$-coloring against adaptive adversaries drops from $\widetilde{O}(n^{8/9})$ to $\widetilde{O}(n^{2/3})$, a polynomial improvement for every $n$.
The analysis identifies $n^{2/3}$ as a natural barrier for algorithms based on random color trials and phase-based slack, so obtaining $o(n^{2/3})$ would require a fundamentally different source of available colors.
The inlier/outlier dichotomy for recoloring dense clusters is stated as a technique of independent interest, potentially reusable in other dynamic or distributed coloring settings where dense regions are the bottleneck.
Because the algorithm tolerates adaptive adversaries, its correctness and high-probability guarantees survive when updates are interleaved with the algorithm's own recoloring decisions, making it usable in interactive or online settings.

Reading between the lines

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

The four-layer decomposition matches the order in which streaming and distributed algorithms build colorings; one could test whether the same average-density criterion improves bounds in those models, since the paper itself notes the structural inspiration.
The color-stealing chain resembles augmenting paths in a palette graph; formalizing it as a path-length argument might give a more precise trade-off between the number of stolen colors and update time.
The paper leaves open whether the phase length and the parameter $\zeta$ can be tuned further; a natural experiment is to implement the algorithm with $\Delta \approx n^{2/3}$ and measure the actual amortized cost of the refresh step versus the recoloring steps, which would show how tight the balance is.

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.

Desk Editor's Note

read the letter

Bottom line: this is a serious paper with a genuinely new high-level approach, but the main theorem is not proven as written. The two invariant-maintenance bugs are internal and load-bearing.

What's good: the average-density sparser-denser decomposition (Section 3) is a real improvement over BRW25's uniform epsilon; it lets the algorithm treat dense vertices with inliers/outliers separately, and the simplified colorful matching is cleaner. The proof of Lemma 3.6 is self-contained and readable. If the invariants held, the runtime analysis in Section 4.4 would likely go through.

The problem: Lemma 4.3's claim about RecolorDense is false on the stated pseudocode. Algorithm 3 line 5 rejects a sampled color only if it is used by a neighbor outside I_D; it does not reject colors used by non-neighbor outliers in D. So an outlier v can be colored with chi already held by an outlier u that is not adjacent to v. If no inlier uses chi, line 7 colors v with chi. Now two vertices share a color in D but M_D and matched[] are not updated. Repeat this once more and three vertices share a color, violating Dense Balance. The proof in Lemma 4.5 also misreads lines 4-5 as excluding phi(O_D), which they don't.

Second, RecolorMatching (Algorithm 4) adds the new color to M_D but never removes the color that the matched pair had before. If u and v were the only holders of their old color, M_D now contains a color that no vertex has. This inflates |M_D|, so IncrMatching may not be called when the actual repeated-color count drops, and the Accounting Lemma's use of M as number of repeated colors is no longer valid.

Both issues are internal, not about the imported [BRW25] decomposition. Dense Balance is exactly what bounds |Phi[chi]| in Section 4.4; without it the tilde-O(n^{2/3}) amortized time is unsupported.

I think the paper deserves a serious referee because the ideas are valuable and the bugs look fixable—e.g., make RecolorDense reject any color already used in D (except the one inlier to steal), and maintain M_D properly in RecolorMatching. But as submitted, the main claim doesn't stand.

Reading group: maybe, as a case study in how randomized invariants can silently break. I would not cite it in its current form.

Referee Report

2 major / 4 minor

Summary. This paper presents a randomized fully dynamic algorithm for maintaining a proper (Δ+1)-coloring of an n-vertex graph under edge insertions and deletions, with updates chosen by an adaptive adversary, and claims amortized update time Õ(n^{2/3}) with high probability. The algorithm works in phases: at each phase boundary it recomputes a fresh coloring, and within a phase it maintains an (ε,ζ)-sparser-denser decomposition, recolors sparser vertices by random color trials, maintains a matching of repeated colors in each dense cluster, and distinguishes inliers from outliers to keep the cost of recoloring dense vertices small. The central runtime accounting in Section 4.4 combines a sparse color-class bound (Lemma 4.9) with the Dense Balance Invariant to show that every color class has size O(n/ζ)=O(n^{1/3}), yielding the claimed bound.

Significance. If the proof is completed, the result would improve the state of the art for fully dynamic (Δ+1)-coloring against adaptive adversaries from Õ(n^{8/9}) to Õ(n^{2/3}), matching a natural barrier discussed in the paper. The paper is well structured, gives explicit constants (ε=1/110, ζ=n^{2/3}), and its main claim is not circular: Proposition 3.7 is an imported published theorem used as a tool, and the runtime analysis is explicit rather than fitted to the target bound. The inlier/outlier color-stealing scheme and the use of average sparsity in the decomposition are potentially useful ideas. However, the current pseudocode has a concrete invariant-maintenance gap that invalidates the Dense Balance bound used in the proof of Theorem 1; this gap is internal to the paper and must be repaired before the main claim is established.

major comments (2)

[Section 4, Algorithm 3 (RecolorDense), Lemma 4.3] The else branch at line 7 of RecolorDense is not covered by the case analysis in Lemma 4.3. In RecolorDense(v) for an outlier v, line 4 rejects only colors in M_D, and line 5 rejects only colors held by a vertex u with u∈N(v) and u∉I_D. A color χ held by a single unmatched outlier u with u∉N(v), and with no inlier holding χ, passes both tests, fails the line 6 singleton-inlier test, and reaches line 7, so v is colored with χ. This creates a repeated color in D without setting matched[u], matched[v], or adding χ to M_D. If a second, similarly non-adjacent outlier later samples the same χ, the same path can color a third vertex with χ, violating the Dense Balance Invariant (each color appears at most twice in each cluster). Lemma 4.3's statement that RecolorDense colors v with a color 'either unused in D or used by an unmatched inlier' is therefore false for the pseudocode as written. Since the proof of Theorem 1 in Section 4.4 uses Dense Balance to bound |D_i∩Φ[χ]|≤2 and hence |Φ[χ]|≤|Φ[χ]∩S|+4n/Δ, the claimed Õ(n^{2/3}) amortized update time is not established by the current algorithm. The fix must either reject such colors or explicitly match v with the singleton outlier and maintain M_D and the matched pointers accordingly.
[Section 4, Algorithm 4 (RecolorMatching), Lemma 4.5 and Lemma 4.6] RecolorMatching adds χ to M_D in line 6 but never deletes the previous color of the matched pair u,v when those vertices are recolored. Such recoloring happens in line 12 of RecolorInsert and in line 9 of RecolorSparse, so after those calls M_D can contain a color that is no longer used by any vertex of D. Because Lemma 4.5 and the Accounting Lemma (Lemma 3.9) treat |M_D| as the number of actual redundant colors, stale entries can make |M_D| larger than the true number of repeated colors; the claimed lower bound |L(D)∩L(v)|≥1 for inliers may then fail, and the runtime bound of RecolorDense for inliers is unsupported. The procedure should remove the old repeated color from M_D when a matched pair changes color, and the proof of Lemma 4.6 should account for this maintenance.

minor comments (4)

[Lemma 4.2] The statement says that aD and eD increase or decrease by at most one within a phase, but the proof bounds the change by an additive t/|D|≤2ε; please align the statement with the proof.
[Section 4 and Section 5] Proposition 4.1 is stated in Section 4 and then stated again at the start of Section 5; renumber or refer back to avoid duplicate numbering.
[Section 4.4] The phrase 'each of the at most 2n/Δ almost-cliques' should be justified by explicitly noting the lower bound |D_i|≥(1−ε)Δ, which is implicit in the definition of an ε-almost-clique.
[Algorithm 4] When RecolorMatching is called on an already matched pair, line 2 leaves the matched pointers unchanged; the text should clarify that the pair remains matched after recoloring, since the current pseudocode only initializes matched pointers for previously unmatched endpoints.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation found: the main runtime theorem is derived from an external decomposition black box plus independent invariant arguments, and the self-citations are auxiliary rather than load-bearing.

full rationale

I examined the derivation chain of Theorem 1 for self-definition, fitted-input-called-prediction, self-citation load-bearing steps, imported uniqueness, ansatz smuggling, and renamed known results. No such step appears. The central new ingredient is the sparser-denser decomposition of Section 3, maintained via Lemma 3.5 by invoking Proposition 3.7, which is explicitly quoted as an external result: 'Proposition 3.7 ([BRW25, Theorem 4.1])'. This is not a self-citation, and it is not equivalent to the paper's own dynamic-coloring theorem; it is a black-box subroutine for maintaining an almost-clique decomposition. The final bound eO(n^{2/3}) comes from instantiating the free parameters as ε = 1/110 and ζ = n^{2/3} in the phase analysis of Section 4.4, not from assuming the conclusion. The self-citations that do appear — [HKMT21, Lemma 6.2] and [HNT21, Lemma 3] inside Lemma 3.6 — are used as published structural facts about sparsity of vertices in almost-cliques. The external-degree part is even re-proved in the text ('A proof of this fact has already appeared in a technical report by Halldórsson, Nolin and Tonoyan [HNT21, Lemma 3]. Since it is a short and important proof, we include it here for completeness'), and the anti-neighbor part is an independent lemma from a published paper, not a restatement of Theorem 1. Proposition 5.1, used to generate slack in the fresh coloring, is attributed to the distributed-coloring literature ([ACK19], [BRW25], [HKMT21]) and concerns one-shot random coloring; it does not presuppose the adaptive dynamic algorithm being proved. The Accounting Lemma 3.9 is proved directly from the definition of colorful matching and clique palette, and the dense invariants are proved by induction in Lemmas 4.3 and 4.4. No parameter is fitted to data and then renamed a prediction; the algorithm does not involve any such fitting. I also considered the reviewer concern about a possible failure of the Dense Balance invariant in Algorithm 3's else branch, but that is a correctness/invariant-maintenance issue about the pseudocode, not a circularity of the kind this pass is asked to detect. Therefore the paper's derivation is self-contained with respect to circularity, and the appropriate score is 0.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The algorithm introduces no new physical or mathematical entities. Its main numerical choices (ε, ζ, phase length t) are hand-set constants or functions of n chosen to balance terms in the amortized analysis; they are not fitted to observations. The proof relies on several imported structural lemmas from the dynamic/distributed coloring literature (BRW25, HKMT21, CLP20/MR02) plus standard Chernoff bounds.

free parameters (4)

ε (almost-clique parameter) = 1/110
Hand-set constant in Theorem 1 proof; determines the sparser-denser decomposition. Chosen for the proof, not fitted to external data.
ζ (sparsity threshold) = n^{2/3}
Chosen to optimize the amortized update bound; balances refresh cost and per-update recoloring cost.
γ (phase length constant) = unspecified universal constant (Proposition 4.1)
Phase length is t = γζ; existence proven, explicit value not needed for the bound.
δ (decomposition constant) = unspecified universal constant (Lemma 3.5)
Appears in the sparsity guarantees and in the threshold for the naive algorithm when Δ is small.

assumptions (5)

domain assumption Proposition 3.7 from [BRW25], a dynamic almost-clique decomposition with O(η^{-4} log n) amortized update time against an adaptive adversary.
Imported as a black box; used in Lemma 3.5 to maintain the sparser-denser decomposition. Load-bearing for the whole algorithm.
domain assumption Lemma 6.2 from [HKMT21]: a vertex with anti-degree a_v is at least (1-3ε)/2·a_v-sparse.
Used in Lemma 3.6 to show filtered dense vertices are ζ-sparse.
domain assumption Proposition 5.1 (OneShotColoring slack lemma), from [CLP20], [HKMT21], [MR02].
Used in Lemma 5.2 to establish Sparse Slack after the initial random coloring.
standard math Chernoff bounds with stochastic domination (Lemma A.1), from [DP09], [Doe20], [KQ21].
Used throughout for high-probability concentration with adaptively chosen random variables.
domain assumption The problem setting: simple undirected graph on fixed n vertices, maximum degree Δ known in advance, degree never exceeds Δ.
Defines the model and ensures the palette size Δ+1 is fixed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Faster Dynamic $(\Delta+1)$-Coloring Against Adaptive Adversaries." pith.science (2026). https://pith.science/paper/ZO5O52D2

@misc{pith2026250419729,
  author       = {Pith},
  title        = {Pith review of: Faster Dynamic $(\Delta+1)$-Coloring Against Adaptive Adversaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZO5O52D2}},
  note         = {Machine review of arXiv:2504.19729}
}

abstract

We consider the problem of maintaining a proper $(\Delta + 1)$-vertex coloring in a graph on $n$-vertices and maximum degree $\Delta$ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time $\widetilde{O}( n^{2/3} )$ against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent $\widetilde{O}( n^{8/9} )$-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic $(\Delta+1)$-coloring algorithms. The main improvements are in the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 10 canonical work pages

[1]

In Ioana Oriana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 1–8

vertex coloring via asymmetric palette sparsification. In Ioana Oriana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 1–8. SIAM,

work page 2025
[10]

Halld´ orsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan

[HKMT21] Magn´ us M. Halld´ orsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. Efficient randomized distributed coloring in CONGEST. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1180–1193. ACM,

work page 2021
[11]

Halld´ orsson, Alexandre Nolin, and Tigran Tonoyan

[HNT21] Magn´ us M. Halld´ orsson, Alexandre Nolin, and Tigran Tonoyan. Ultrafast distributed coloring of high degree graphs. CoRR, abs/2105.04700,

arXiv
[2009]

(2∆ - l)-edge-coloring is much easier than maximal matching in the distributed setting

[EPS15] Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2∆ - l)-edge-coloring is much easier than maximal matching in the distributed setting. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 355–370. SIAM,

work page 2015
[2015]

Halld´ orsson, Fabian Kuhn, and Alexandre Nolin

[FGH+23] Maxime Flin, Mohsen Ghaffari, Magn´ us M. Halld´ orsson, Fabian Kuhn, and Alexandre Nolin. Coloring fast with broadcasts. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023, Orlando, FL, USA, June 17-19, 2023 , pages 455–465. ACM,

work page 2023
[2018]

The multiplicative version of azuma’s inequality, with an application to contention analysis

[KQ21] William Kuszmaul and Qi Qi. The multiplicative version of azuma’s inequality, with an application to contention analysis. CoRR, abs/2102.05077,

arXiv
[2020]

FASTER DYNAMIC (∆ + 1)-COLORING AGAINST ADAPTIVE ADVERSARIES 19 [CMNS24] Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, and Farrel D. Salim. Round and communi- cation efficient graph coloring. CoRR, abs/2412.12589,

work page Pith review arXiv
[2021]

The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local com- putation

[CFG+19] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local com- putation. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Ca...

work page 2019

Show all 12 references

[2022]

Fully dynamic (∆ + 1)-coloring against adaptive adversaries

[BRW25] Soheil Behnezhad, Rajmohan Rajaraman, and Omer Wasim. Fully dynamic (∆ + 1)-coloring against adaptive adversaries. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, ...

2025
[2023]

Halld´ orsson, Fabian Kuhn, and Alexandre Nolin

[FGH+24] Maxime Flin, Mohsen Ghaffari, Magn´ us M. Halld´ orsson, Fabian Kuhn, and Alexandre Nolin. A distributed palette sparsification theorem. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024 . SIAM,

2024
[2024]

(∆+1) vertex coloring in O(n) communication

[FM24] Maxime Flin and Parth Mittal. (∆+1) vertex coloring in O(n) communication. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024 , pages 416–424. ACM,

2024
[2025]

Dynamic algorithms for graph coloring

[BCHN18] Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Janua...

2018

Pith tools

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

[1] [1]

In Ioana Oriana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 1–8

vertex coloring via asymmetric palette sparsification. In Ioana Oriana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 1–8. SIAM,

work page 2025

[2] [10]

Halld´ orsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan

[HKMT21] Magn´ us M. Halld´ orsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. Efficient randomized distributed coloring in CONGEST. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1180–1193. ACM,

work page 2021

[3] [11]

Halld´ orsson, Alexandre Nolin, and Tigran Tonoyan

[HNT21] Magn´ us M. Halld´ orsson, Alexandre Nolin, and Tigran Tonoyan. Ultrafast distributed coloring of high degree graphs. CoRR, abs/2105.04700,

arXiv

[4] [2009]

(2∆ - l)-edge-coloring is much easier than maximal matching in the distributed setting

[EPS15] Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2∆ - l)-edge-coloring is much easier than maximal matching in the distributed setting. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 355–370. SIAM,

work page 2015

[5] [2015]

Halld´ orsson, Fabian Kuhn, and Alexandre Nolin

[FGH+23] Maxime Flin, Mohsen Ghaffari, Magn´ us M. Halld´ orsson, Fabian Kuhn, and Alexandre Nolin. Coloring fast with broadcasts. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023, Orlando, FL, USA, June 17-19, 2023 , pages 455–465. ACM,

work page 2023

[6] [2018]

The multiplicative version of azuma’s inequality, with an application to contention analysis

[KQ21] William Kuszmaul and Qi Qi. The multiplicative version of azuma’s inequality, with an application to contention analysis. CoRR, abs/2102.05077,

arXiv

[7] [2020]

FASTER DYNAMIC (∆ + 1)-COLORING AGAINST ADAPTIVE ADVERSARIES 19 [CMNS24] Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, and Farrel D. Salim. Round and communi- cation efficient graph coloring. CoRR, abs/2412.12589,

work page Pith review arXiv

[8] [2021]

The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local com- putation

[CFG+19] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local com- putation. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Ca...

work page 2019