pith. sign in

arxiv: 2604.20836 · v1 · submitted 2026-04-22 · 💻 cs.DS

Dynamic Construction of the Lov\'asz Local Lemma

Bernhard Haeupler , Slobodan Mitrovi\'c , Srikkanth Ramachandran , Wen-Horng Sheu , Robert Tarjan This is my paper

Pith reviewed 2026-05-09 22:59 UTC · model grok-4.3

classification 💻 cs.DS
keywords dynamic algorithmsLovász Local Lemmalocal searchadaptive adversaryconstraint satisfactionresamplingedge coloringwitness trees
0
0 comments X

The pith

Local search algorithms for the Lovász Local Lemma continue to converge with amortized constant steps per update even under fully dynamic adversarial changes to constraints.

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

The paper shows that the same local resampling and backtracking procedures already known to solve many constraint satisfaction problems efficiently on static inputs also work when an adaptive adversary adds or removes constraints over time. These procedures fix violations by resampling variables or unassigning them, and the total number of such steps across all updates stays near-linear in the number of changes. A reader would care because this removes the need to design new algorithms for changing inputs in applications such as graph coloring and scheduling. The argument relies on carrying over the witness-tree and entropy-compression analyses from the static case without extra conditions on the adversary or the constraint structure.

Core claim

A wide class of local search algorithms that either extend partial valid assignments with backtracking or iteratively resample variables to fix violated constraints extend directly to the fully dynamic setting. When an adaptive adversary adds or removes constraints, applying the identical procedures produces a total number of resampling or backtracking steps that is near-linear in the number of updates. The witness-tree and entropy-compression arguments that bound the number of steps on static instances continue to hold without requiring further restrictions on how the adversary chooses updates or on the structure of the constraint hypergraph.

What carries the argument

Local resampling and backtracking procedures for fixing violated constraints, analyzed via witness trees and entropy compression.

If this is right

  • For maximum degree Δ equal to a polynomial in log n, a (1+ε)Δ-edge coloring can be maintained with poly(log n) amortized update time against an adaptive adversary.
  • The same local procedures apply to any constraint satisfaction problem previously solvable via static local search under the Lovász Local Lemma.
  • The total number of fixing steps remains near-linear in the number of adversarial updates across the entire sequence.
  • No redesign of the core local search loop is required when moving from static to fully dynamic inputs.

Where Pith is reading between the lines

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

  • The result suggests that other local-search-based algorithms outside the Lovász Local Lemma setting may also extend to dynamic inputs with similar amortized bounds.
  • It opens the possibility of maintaining approximate solutions to additional problems such as hypergraph coloring or satisfiability under continuous adversarial changes.
  • The approach may combine with existing dynamic data structures to reduce the per-update overhead even further in practice.

Load-bearing premise

The witness-tree and entropy-compression analyses developed for static instances carry over to the dynamic case without extra restrictions on the adaptive adversary or the constraint hypergraph.

What would settle it

A concrete dynamic sequence of constraint additions and removals on a hypergraph that satisfies the static Lovász Local Lemma conditions, yet forces the local search procedure to perform more than near-linear total steps in the number of updates.

read the original abstract

This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized $\tilde{O}(1)$ number of local-search steps per update. A breakthrough by Moser (2009) introduced the witness-tree and entropy compression techniques for analyzing local resampling processes for the Lov\'asz Local Lemma. These methods have since been generalized and expanded to analyze a wide variety of local search algorithms that can efficiently find solutions to many important local constraint satisfaction problems. These algorithms either extend a partial valid assignment and backtrack by unassigning variables when constraints become violated, or they iteratively fix violated constraints by resampling their variables. These local resampling or backtracking procedures are incredibly flexible, practical, and simple to specify and implement. Yet, they can be shown to be extremely efficient on static instances, typically performing only (sub)-linear number of fixing steps. The main technical challenge lies in proving conditions that guarantee such rapid convergence. This paper extends these convergence results to fully dynamic settings, where an adaptive adversary may add or remove constraints. We prove that applying the same simple local search procedures to fix old or newly introduced violations leads to a total number of resampling steps near-linear in the number of adversarial updates. Our result is very general and yields several immediate corollaries. For example, letting $\Delta$ denote the maximum degree, for a constant $\epsilon$ and $\Delta = \text{poly}(\log n)$, we can maintain a $(1+\epsilon) \Delta$-edge coloring in $\text{poly}(\log n)$ amortized update time against an adaptive adversary. The prior work for this regime has exponential running time in $\sqrt{\log n}$ [Christiansen, SODA '26].

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

3 major / 2 minor

Summary. The paper claims that a wide class of local search algorithms for the Lovász Local Lemma—those analyzed via witness trees or entropy compression in the static case—extend directly to the fully dynamic setting against an adaptive adversary. These algorithms achieve an amortized Õ(1) number of resampling or backtracking steps per update (insertion or deletion of constraints). The result is presented as general, with immediate corollaries including a poly(log n) amortized update-time algorithm for (1+ε)Δ-edge coloring when Δ = poly(log n), improving on prior exponential-in-√log n bounds.

Significance. If the central claim is correct, the work would be significant for dynamic algorithms and algorithmic LLL applications. It would show that simple, practical local-search procedures remain efficient under adversarial updates without modification, enabling new dynamic maintenance results for CSPs and graph problems. The generality across multiple LLL algorithms and the concrete improvement for edge coloring are strengths; the paper also credits the Moser 2009 witness-tree technique as the foundation.

major comments (3)
  1. [§3] §3 (Main Dynamic Theorem): the argument that static witness-tree and entropy-compression bounds carry over verbatim to the dynamic case must explicitly handle an adaptive adversary that selects each new constraint after observing the current partial assignment and prior resampling history. The provided abstract and high-level description do not contain a lemma showing that the total number of steps remains O(U) (U = number of updates) rather than growing with path-dependent conditioning on bad-event probabilities.
  2. [Proof of amortized bound] Proof of amortized bound (around the telescoping sum or potential argument): it is not shown that the length of witness trees or the entropy-compression cost remains bounded independently of the adversary's choices. If the adversary can force constraints whose violation probability is conditioned on already-resampled variables, the static analysis may no longer guarantee that the sum of resampling steps across all updates is near-linear in U.
  3. [Corollary 1] Corollary 1 (dynamic edge coloring): the claim of poly(log n) amortized time assumes the LLL criterion (e.g., ep(Δ+1) < 1) continues to hold after each adaptive insertion. No argument is given that insertions chosen by the adversary cannot increase effective degree or violate the symmetric LLL condition in a way that invalidates the per-update Õ(1) bound.
minor comments (2)
  1. [Abstract] The abstract states that 'several immediate corollaries' follow but only details the edge-coloring result; listing the others briefly would improve readability.
  2. [Notation] Notation for amortized Õ(1) should be defined explicitly (e.g., total steps = O(U log^O(1) U) or similar) when first introduced.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify places where the handling of adaptive adversaries and the invariance of the static bounds need to be stated more explicitly. We address each point below and will revise the manuscript to incorporate the requested clarifications and a new lemma.

read point-by-point responses

  1. Referee: [§3] §3 (Main Dynamic Theorem): the argument that static witness-tree and entropy-compression bounds carry over verbatim to the dynamic case must explicitly handle an adaptive adversary that selects each new constraint after observing the current partial assignment and prior resampling history. The provided abstract and high-level description do not contain a lemma showing that the total number of steps remains O(U) (U = number of updates) rather than growing with path-dependent conditioning on bad-event probabilities.

    Authors: We agree that an explicit lemma is needed. In the proof of Theorem 3.1 the witness-tree (or entropy-compression) argument is applied to the global execution trace that concatenates all resamplings triggered by the sequence of U updates. Each update introduces at most one new bad event whose variables are resampled uniformly at random; because resampling is memoryless, any prior conditioning on those variables is erased. Consequently the probability of any witness tree of size k remains bounded by the same static quantity used in the Moser–Tardos analysis, independently of the adversary’s adaptive choices. Summing the expected number of such trees over the entire history yields a total of O(U) resamplings in expectation. We will insert a new Lemma 3.2 that isolates this argument and states the O(U) bound formally. revision: yes

  2. Referee: [Proof of amortized bound] Proof of amortized bound (around the telescoping sum or potential argument): it is not shown that the length of witness trees or the entropy-compression cost remains bounded independently of the adversary's choices. If the adversary can force constraints whose violation probability is conditioned on already-resampled variables, the static analysis may no longer guarantee that the sum of resampling steps across all updates is near-linear in U.

    Authors: The referee is right that the current write-up leaves this invariance implicit. The key property is that every resampling step draws fresh uniform random values for the involved variables, so the marginal probability of any bad event is still at most p regardless of the history or the adversary’s conditioning. The telescoping sum (or potential) therefore continues to bound the expected cost per bad event by a constant that depends only on p and the dependency degree, not on which particular constraints the adversary elects to insert. We will add a short paragraph immediately after the potential-function argument that records this observation and notes that the same constant appears in every update. revision: yes

  3. Referee: [Corollary 1] Corollary 1 (dynamic edge coloring): the claim of poly(log n) amortized time assumes the LLL criterion (e.g., ep(Δ+1) < 1) continues to hold after each adaptive insertion. No argument is given that insertions chosen by the adversary cannot increase effective degree or violate the symmetric LLL condition in a way that invalidates the per-update Õ(1) bound.

    Authors: We will revise the statement of Corollary 1 to make the modeling assumption explicit: the adaptive adversary is permitted to insert or delete edges only while the maximum degree remains at most Δ = poly(log n). Under this promise the symmetric LLL condition ep(Δ+1) < 1 is preserved at every step, so the per-update Õ(1) resampling bound continues to apply. If an insertion would raise the degree above Δ it falls outside the scope of the corollary (as is standard for parameterized dynamic graph problems). A clarifying sentence will be added to the paragraph following the corollary. revision: yes

Circularity Check

0 steps flagged

Static witness-tree and entropy-compression analyses treated as independent inputs for dynamic extension

full rationale

The paper's derivation applies the existing Moser (2009) witness-tree technique and subsequent generalizations of entropy compression directly to each adversarial update, claiming that the same local-search procedures yield amortized Õ(1) resamplings per update. These static convergence results are invoked as given external inputs rather than re-derived or fitted within the paper. No load-bearing step reduces a dynamic bound to a self-defined parameter, a fitted subset of data, or a self-citation chain whose validity depends on the present work. The argument therefore remains self-contained against the cited external benchmarks, producing only a minor self-citation score consistent with normal scholarly practice.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are identifiable from the provided text.

pith-pipeline@v0.9.0 · 5641 in / 1023 out tokens · 21017 ms · 2026-05-09T22:59:40.622551+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

108 extracted references · 16 canonical work pages · 2 internal anchors

  1. [1]

    Anders Johansson

    Asymptotic choice number for triangle free graphs , author = "Anders Johansson", number =. 1996 , institution =

    1996

  2. [2]

    Pettie, Seth and Su, Hsin-Hao , title =. Inf. Comput. , month = aug, pages =. 2015 , issue_date =

    2015

  3. [3]

    Diskret analiz , volume=

    On an estimate of the chromatic class of a p-graph , author=. Diskret analiz , volume=

  4. [4]

    2025 , eprint=

    Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems , author=. 2025 , eprint=

    2025

  5. [5]

    Harris , title =

    Bernhard Haeupler and David G. Harris , title =. 2017 , url =. doi:10.1145/3147211 , timestamp =

    work page doi:10.1145/3147211 2017

  6. [6]

    Leighton, F. T. and Maggs, Bruce M. and Rao, Satish B. , title=. Combinatorica , year=. doi:10.1007/BF01215349 , url=

    work page doi:10.1007/bf01215349

  7. [7]

    and Leiserson, Charles E

    Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , title =. 2009 , isbn =

    2009

  8. [8]

    Beyond the Lov

    Achlioptas, Dimitris and Iliopoulos, Fotis and Sinclair, Alistair , booktitle=. Beyond the Lov. 2019 , organization=

    2019

  9. [9]

    Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    (2 —l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting , author=. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2014 , organization=

    2014

  10. [10]

    Theoretical Computer Science , volume=

    Near-optimal, distributed edge colouring via the nibble method , author=. Theoretical Computer Science , volume=. 1998 , publisher=

    1998

  11. [11]

    and Tardos, G\'

    Moser, Robin A. and Tardos, G\'. A constructive proof of the general lov\'. J. ACM , month = feb, articleno =. 2010 , issue_date =. doi:10.1145/1667053.1667060 , abstract =

    work page doi:10.1145/1667053.1667060 2010

  12. [12]

    The list chromatic number of graphs with small clique number , journal =

    Michael Molloy , keywords =. The list chromatic number of graphs with small clique number , journal =. 2019 , issn =. doi:https://doi.org/10.1016/j.jctb.2018.06.007 , url =

    work page doi:10.1016/j.jctb.2018.06.007 2019

  13. [13]

    1978 , issn =

    Chromatic number, girth and maximal degree , journal =. 1978 , issn =. doi:https://doi.org/10.1016/0012-365X(78)90102-4 , url =

    work page doi:10.1016/0012-365x(78)90102-4 1978

  14. [14]

    Combinatorics, Probability and Computing , author=

    On Brooks’ Theorem for Sparse Graphs , volume=. Combinatorics, Probability and Computing , author=. 1995 , pages=. doi:10.1017/S0963548300001528 , number=

    work page doi:10.1017/s0963548300001528 1995

  15. [15]

    International Conference on Integer Programming and Combinatorial Optimization , pages=

    A Simpler Proof for Packet Routing , author=. International Conference on Integer Programming and Combinatorial Optimization , pages=. 2013 , organization=

    2013

  16. [16]

    Improved distributed algorithms for the lov

    Davies, Peter , booktitle=. Improved distributed algorithms for the lov. 2023 , organization=

    2023

  17. [17]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Deterministic Dynamic Edge Colouring , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  18. [18]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Dynamic edge coloring with improved approximation , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  19. [19]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    The power of multi-step Vizing chains , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  20. [20]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  21. [21]

    Procedia Computer Science , volume=

    Fully-dynamic graph algorithms with sublinear time inspired by distributed computing , author=. Procedia Computer Science , volume=. 2017 , publisher=

    2017

  22. [22]

    ACM Computing Surveys (CSUR) , volume=

    Randomized algorithms , author=. ACM Computing Surveys (CSUR) , volume=. 1996 , publisher=

    1996

  23. [23]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    The complexity of distributed edge coloring with small palettes , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  24. [25]

    Problems and results on 3-chromatic Hypergraphs and some related questions , volume =

    Erdős, Paul and László, Lovász , year =. Problems and results on 3-chromatic Hypergraphs and some related questions , volume =

  25. [26]

    Discrete Mathematics , volume=

    Asymptotic lower bounds for Ramsey functions , author=. Discrete Mathematics , volume=. 1977 , publisher=

    1977

  26. [27]

    An algorithmic approach to the

    Beck, J. An algorithmic approach to the. Random Structures & Algorithms , volume=. 1991 , publisher=

    1991

  27. [28]

    Proceedings of the twenty-first annual ACM symposium on Theory of computing , pages=

    On the complexity of radio communication , author=. Proceedings of the twenty-first annual ACM symposium on Theory of computing , pages=

  28. [29]

    Random Structures & Algorithms , volume=

    A parallel algorithmic version of the local lemma , author=. Random Structures & Algorithms , volume=. 1991 , publisher=

    1991

  29. [30]

    Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

    Static and dynamic path selection on expander graphs (preliminary version) a random walk approach , author=. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

  30. [31]

    Discrete Applied Mathematics , volume=

    Lopsided Lovsz local lemma and Latin transversals , author=. Discrete Applied Mathematics , volume=

  31. [32]

    Combinatorica , volume=

    Improved bounds for acyclic job shop scheduling , author=. Combinatorica , volume=. 2002 , publisher=

    2002

  32. [33]

    SIAM Journal on Computing , volume=

    New algorithmic aspects of the Local Lemma with applications to routing and partitioning , author=. SIAM Journal on Computing , volume=. 2001 , publisher=

    2001

  33. [34]

    An extension of the Lov

    Srinivasan, Aravind , journal=. An extension of the Lov. 2006 , publisher=

    2006

  34. [35]

    Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages=

    Further algorithmic aspects of the local lemma , author=. Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages=

  35. [36]

    Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov

    Czumaj, Artur and Scheideler, Christian , journal=. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov. 2000 , publisher=

    2000

  36. [37]

    A new algorithm approach to the general Lov

    Czumaj, Artur and Scheideler, Christian , booktitle=. A new algorithm approach to the general Lov

  37. [38]

    Improved algorithmic versions of the Lov

    Srinivasan, Aravind , booktitle=. Improved algorithmic versions of the Lov

  38. [39]

    1978 , issn =

    Covering the vertex set of a graph with subgraphs of smaller degree , journal =. 1978 , issn =. doi:https://doi.org/10.1016/0012-365X(78)90147-4 , url =

    work page doi:10.1016/0012-365x(78)90147-4 1978

  39. [40]

    1978 , issn =

    A bound on the chromatic number of a graph , journal =. 1978 , issn =. doi:https://doi.org/10.1016/0012-365X(78)90049-3 , url =

    work page doi:10.1016/0012-365x(78)90049-3 1978

  40. [41]

    1977 , issn =

    On an upper bound of a graph's chromatic number, depending on the graph's degree and density , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0095-8956(77)90037-5 , url =

    work page doi:10.1016/0095-8956(77)90037-5 1977

  41. [42]

    Russian Mathematical Surveys , abstract =

    V G Vizing , title =. Russian Mathematical Surveys , abstract =. 1968 , month =. doi:10.1070/RM1968v023n06ABEH001252 , url =

    work page doi:10.1070/rm1968v023n06abeh001252 1968

  42. [43]

    , title =

    Brooks, R.L. , title =. 1941 , journal =. doi:10.1017/S030500410002168X , url =

    work page doi:10.1017/s030500410002168x 1941

  43. [44]

    A constructive proof of the Lov

    Moser, Robin A , booktitle=. A constructive proof of the Lov

  44. [45]

    ACM Journal of the ACM (JACM) , volume=

    A framework for adversarially robust streaming algorithms , author=. ACM Journal of the ACM (JACM) , volume=. 2022 , publisher=

    2022

  45. [46]

    2026 , journal=

    Assadi, Sepehr and Yazdanyar, Helia , title =. 2026 , journal=

    2026

  46. [48]

    Annual International Cryptology Conference , pages=

    Separating adaptive streaming from oblivious streaming using the bounded storage model , author=. Annual International Cryptology Conference , pages=. 2021 , organization=

    2021

  47. [49]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  48. [50]

    19th Scandinavian Symposium on Algorithm Theory , pages=

    Arboricity-Dependent Algorithms for Edge Coloring , author=. 19th Scandinavian Symposium on Algorithm Theory , pages=

  49. [51]

    19th Scandinavian Symposium on Algorithm Theory , year=

    Sparsity-Parameterised Dynamic Edge Colouring , author=. 19th Scandinavian Symposium on Algorithm Theory , year=

  50. [53]

    ACM Transactions on Algorithms (TALG) , volume=

    Improved dynamic graph coloring , author=. ACM Transactions on Algorithms (TALG) , volume=. 2020 , publisher=

    2020

  51. [54]

    2026 , journal=

    Maintaining Random Assignments under Adversarial Dynamics , author=. 2026 , journal=

    2026

  52. [55]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Dynamic algorithms for graph coloring , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  53. [56]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Faster vizing and near-vizing edge coloring algorithms , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  54. [57]

    Theoretical Computer Science , volume=

    Fast and simple (1+ ) -edge-coloring of dense graphs , author=. Theoretical Computer Science , volume=. 2025 , publisher=

    2025

  55. [60]

    On the complexity of radio communication

    Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. On the complexity of radio communication. In Proceedings of the twenty-first annual ACM symposium on Theory of computing , pages 274--285, 1989

    1989

  56. [61]

    Beyond the lov \'a sz local lemma: Point to set correlations and their algorithmic applications

    Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the lov \'a sz local lemma: Point to set correlations and their algorithmic applications. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 725--744. IEEE, 2019

    2019

  57. [62]

    A parallel algorithmic version of the local lemma

    Noga Alon. A parallel algorithmic version of the local lemma. Random Structures & Algorithms , 2(4):367--378, 1991

    1991

  58. [63]

    Faster vizing and near-vizing edge coloring algorithms

    Sepehr Assadi. Faster vizing and near-vizing edge coloring algorithms. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4861--4898. SIAM, 2025

    2025

  59. [64]

    Fully dynamic algorithms for coloring triangle-free graphs

    Sepehr Assadi and Helia Yazdanyar. Fully dynamic algorithms for coloring triangle-free graphs. arXiv preprint , 2026

    2026

  60. [65]

    Separations between oblivious and adaptive adversaries for natural dynamic graph problems, 2025

    Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems, 2025

    2025

  61. [66]

    Dynamic algorithms for graph coloring

    Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1--20. SIAM, 2018

    2018

  62. [67]

    Arboricity-dependent algorithms for edge coloring

    Sayan Bhattacharya, Mart \' n Costa, Nadav Panski, and Shay Solomon. Arboricity-dependent algorithms for edge coloring. In 19th Scandinavian Symposium on Algorithm Theory , page 1, 2024

    2024

  63. [68]

    Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time

    Sayan Bhattacharya, Mart \' n Costa, Nadav Panski, and Shay Solomon. Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3393--3440. SIAM, 2024

    2024

  64. [69]

    A linear-time algorithm for

    Anton Bernshteyn and Abhishek Dhawan. A linear-time algorithm for (1+ ) -edge-coloring. arXiv preprint arXiv:2407.04887 , 2024

    work page arXiv 2024

  65. [70]

    An algorithmic approach to the L ov \'a sz local lemma

    J \'o zsef Beck. An algorithmic approach to the L ov \'a sz local lemma. I . Random Structures & Algorithms , 2(4):343--365, 1991

    1991

  66. [71]

    A framework for adversarially robust streaming algorithms

    Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. ACM Journal of the ACM (JACM) , 69(2):1--33, 2022

    2022

  67. [72]

    Static and dynamic path selection on expander graphs (preliminary version) a random walk approach

    Andrei Z Broder, Alan M Frieze, and Eli Upfal. Static and dynamic path selection on expander graphs (preliminary version) a random walk approach. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages 531--539, 1997

    1997

  68. [73]

    On an upper bound of a graph's chromatic number, depending on the graph's degree and density

    O.V Borodin and A.V Kostochka. On an upper bound of a graph's chromatic number, depending on the graph's degree and density. Journal of Combinatorial Theory, Series B , 23(2):247--250, 1977

    1977

  69. [74]

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds

    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1671--1684, 2022

    2022

  70. [75]

    Fully-dynamic graph algorithms with sublinear time inspired by distributed computing

    Leonid Barenboim and Tzalik Maimon. Fully-dynamic graph algorithms with sublinear time inspired by distributed computing. Procedia Computer Science , 108:89--98, 2017

    2017

  71. [76]

    Chromatic number, girth and maximal degree

    Béla Bollobás. Chromatic number, girth and maximal degree. Discrete Mathematics , 24(3):311--314, 1978

    1978

  72. [77]

    R.L. Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society , 37(2):194 – 197, 1941

    1941

  73. [78]

    Paul A. Catlin. A bound on the chromatic number of a graph. Discrete Mathematics , 22(1):81--83, 1978

    1978

  74. [79]

    The complexity of distributed edge coloring with small palettes

    Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. The complexity of distributed edge coloring with small palettes. arXiv preprint arXiv:1708.04290 , 2017

    work page arXiv 2017

  75. [80]

    The complexity of distributed edge coloring with small palettes

    Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. The complexity of distributed edge coloring with small palettes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2633--2652. SIAM, 2018

    2018

  76. [81]

    The power of multi-step vizing chains

    Aleksander Bj rn Grodt Christiansen. The power of multi-step vizing chains. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1013--1026, 2023

    2023

  77. [82]

    Deterministic dynamic edge colouring

    Aleksander BG Christiansen. Deterministic dynamic edge colouring. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1047--1096. SIAM, 2026

    2026

  78. [83]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition . The MIT Press, 3rd edition, 2009

    2009

  79. [84]

    Sparsity-parameterised dynamic edge colouring

    Aleksander BG Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-parameterised dynamic edge colouring. In 19th Scandinavian Symposium on Algorithm Theory , 2024

    2024

  80. [85]

    Coloring nonuniform hypergraphs: A new algorithmic approach to the general lov \'a sz local lemma

    Artur Czumaj and Christian Scheideler. Coloring nonuniform hypergraphs: A new algorithmic approach to the general lov \'a sz local lemma. Random Structures & Algorithms , 17(3-4):213--237, 2000

    2000

Showing first 80 references.