pith. sign in

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

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Sepehr Assadi , Helia Yazdanyar This is my paper

Pith reviewed 2026-05-09 23:20 UTC · model grok-4.3

classification 💻 cs.DS
keywords dynamic graph algorithmsgraph coloringtriangle-free graphsentropy compressionamortized update timeadaptive adversaryJohansson coloring
0
0 comments X

The pith

A randomized algorithm maintains an O(Δ/lnΔ) proper coloring of triangle-free graphs under edge insertions and deletions in Δ^{o(1)} log n amortized time per update.

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

The paper establishes a fully dynamic method to keep a proper coloring that uses only O(Δ/lnΔ) colors on triangle-free graphs, matching the best static guarantee from Johansson's theorem. The algorithm handles both insertions and deletions while ensuring the coloring stays valid after each change, with randomized amortized updates that depend subpolynomially on the maximum degree Δ and logarithmically on the number of vertices n. This works even when an adversary adapts future updates based on the algorithm's random choices and previous outputs. A sympathetic reader would care because real graphs often evolve through local edge changes, and the result shows that strong non-greedy colorings can be maintained efficiently without restarting the entire computation from scratch each time.

Core claim

The central claim is that there exists a randomized algorithm which, given any sequence of edge insertions and deletions on an n-vertex triangle-free graph that remains triangle-free, maintains a proper O(Δ/lnΔ) coloring with amortized update time Δ^{o(1)} log n per update, with high probability even against an adaptive adversary. The analysis relies on an application of the entropy compression method to bound the number of recoloring steps after each update.

What carries the argument

The entropy compression method, used to analyze the probability that the randomized recoloring procedure after an update performs many steps; it shows that the description length of bad event sequences is too short to occur often.

If this is right

  • The same O(Δ/lnΔ) coloring bound can be maintained dynamically without full recomputation after each update.
  • The update time bound holds with high probability and against adaptive adversaries that see the random choices.
  • Entropy compression provides a general tool for analyzing the number of local changes in randomized dynamic graph algorithms.
  • Both insertions and deletions are supported while preserving the coloring invariant at every step.

Where Pith is reading between the lines

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

  • The entropy compression technique may simplify proofs for other dynamic problems that involve repeated local random choices, such as maintaining matchings or orientations.
  • If implemented, the algorithm could support applications like dynamic frequency assignment in wireless networks where triangle-free interference graphs arise.
  • The subpolynomial dependence on Δ suggests that for graphs with moderate maximum degree the per-update work remains practical even as n grows large.

Load-bearing premise

The input graph remains triangle-free after every edge insertion or deletion, so that the special coloring bound O(Δ/lnΔ) continues to apply.

What would settle it

An explicit sequence of edge insertions and deletions on a triangle-free graph where the algorithm uses more than O(Δ/lnΔ) colors on some intermediate graph or where the average number of recoloring steps per update exceeds Δ^{o(1)} log n with non-negligible probability.

read the original abstract

A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree $\Delta$ can be properly colored with $O(\Delta/\ln\Delta)$ colors, improving upon the "greedy bound" of $\Delta+1$ coloring in general graphs. This coloring can also be found in polynomial time. We present an algorithm for maintaining an $O(\Delta/\ln\Delta)$ coloring of a dynamically changing triangle-free graph that undergoes edge insertions and deletions. The algorithm is randomized and on $n$-vertex graphs has amortized update time of $\Delta^{o(1)}\log{n}$ per update with high probability, even against an adaptive adversary. A key to the analysis of our algorithm is an application of the entropy compression method that to our knowledge is new in the context of dynamic algorithms. This technique appears general and is likely to find other applications in dynamic problems and thus can be of its own independent interest.

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

2 major / 2 minor

Summary. The paper claims a randomized fully-dynamic algorithm that maintains a proper O(Δ / ln Δ) coloring of an n-vertex triangle-free graph with maximum degree Δ under edge insertions and deletions. It achieves amortized update time Δ^{o(1)} log n per update with high probability against an adaptive adversary. The key analytic tool is a new application of the entropy compression method to bound recoloring cascades.

Significance. If correct, the result is significant: it lifts Johansson's static O(Δ / ln Δ) coloring theorem for triangle-free graphs into the fully dynamic setting with near-polylogarithmic amortized updates. The entropy-compression technique is presented as potentially reusable for other dynamic problems, which would be of independent interest.

major comments (2)
  1. [Section 4 (analysis)] The manuscript does not provide a self-contained proof sketch or high-level analysis of how entropy compression is adapted to deletions (as opposed to the more common insertion-only or static settings). A concrete walk-through of the potential function or compression argument under edge deletions would be needed to confirm that the O(Δ / ln Δ) bound is preserved after each update.
  2. [Section 3 (algorithm description)] It is unclear how the algorithm maintains an explicit upper bound on the current Δ after each update while keeping the coloring proper and within the claimed palette size; the dependence of the color count on the instantaneous Δ must be handled without violating the amortized time bound.
minor comments (2)
  1. [Introduction] The abstract and introduction should cite the original Johansson result with a precise reference (e.g., the 1996 paper or its journal version).
  2. [Throughout] Notation for the color palette size (O(Δ / ln Δ)) should be made uniform between the abstract, theorem statements, and analysis sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and for the constructive comments that will help improve the clarity of the manuscript. We address each major comment below and will incorporate revisions to strengthen the presentation of both the algorithm and its analysis.

read point-by-point responses

  1. Referee: [Section 4 (analysis)] The manuscript does not provide a self-contained proof sketch or high-level analysis of how entropy compression is adapted to deletions (as opposed to the more common insertion-only or static settings). A concrete walk-through of the potential function or compression argument under edge deletions would be needed to confirm that the O(Δ / ln Δ) bound is preserved after each update.

    Authors: We agree that the current write-up of the entropy-compression argument in Section 4 would benefit from a more explicit high-level sketch focused on deletions. In the revised manuscript we will add a dedicated subsection that first recalls the static/insertion-only potential function, then walks through the modifications needed for deletions: how an edge deletion relaxes a color constraint, how this affects the local entropy measure, and how the compression argument is applied to bound the expected size of the resulting recoloring cascade. The sketch will include the key inequality showing that the O(Δ / ln Δ) palette size is preserved with high probability after each deletion, together with a short illustrative example of a deletion-induced cascade. This addition will make the adaptation self-contained without altering the underlying analysis. revision: yes

  2. Referee: [Section 3 (algorithm description)] It is unclear how the algorithm maintains an explicit upper bound on the current Δ after each update while keeping the coloring proper and within the claimed palette size; the dependence of the color count on the instantaneous Δ must be handled without violating the amortized time bound.

    Authors: The algorithm maintains an explicit upper bound on Δ by storing vertex degrees in a balanced binary search tree that reports the current maximum in O(log n) time; after each update we compare the new maximum against the previously used Δ_est. The palette size is set to c·Δ_est / ln Δ_est for a sufficiently large constant c that absorbs both the estimation error and the possible degree increase until the next recomputation. Recomputation of Δ_est (and the corresponding palette) occurs only every Θ(log n) updates or when the observed maximum degree exceeds the current estimate by more than a (1+ε) factor; between recomputations the entropy-compression routine is invoked with the fixed palette and resolves any local conflicts in amortized Δ^{o(1)} log n time. We will augment Section 3 with pseudocode for the degree-tracking structure and a short paragraph proving that the extra overhead of occasional palette adjustments remains within the claimed amortized bound. The coloring remains proper at all times because any newly introduced conflicts are immediately resolved by the same compression procedure used for insertions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper claims a constructive randomized dynamic algorithm that maintains an O(Δ/ln Δ) proper coloring of triangle-free graphs under insertions/deletions, with amortized Δ^{o(1)} log n update time w.h.p. The key analytic tool is an application of entropy compression (new to dynamic algorithms per the abstract). The input assumption that the graph remains triangle-free is explicit in the problem statement, Δ is maintained by standard dynamic structures, and the recoloring analysis relies on potential functions and probabilistic bounds that do not reduce to fitted parameters or self-citations. No self-definitional steps, no predictions that are inputs by construction, and no load-bearing uniqueness theorems imported from the authors' prior work appear in the provided abstract or reader summary. The result is presented as an independent algorithmic contribution with external technique.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on Johansson's static coloring result and standard assumptions from randomized algorithm analysis; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Johansson's theorem that triangle-free graphs of maximum degree Δ are O(Δ / ln Δ)-colorable in polynomial time
    The dynamic algorithm builds directly on this static guarantee.
  • standard math Standard probabilistic method and high-probability bounds in randomized algorithms
    Used to analyze the entropy compression and update times.

pith-pipeline@v0.9.0 · 5456 in / 1202 out tokens · 41218 ms · 2026-05-09T23:20:12.483589+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

158 extracted references · 13 canonical work pages · 1 internal anchor

  1. [1]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas , title =. 2006 , isbn =

    2006

  2. [2]

    Ablayev , title =

    Farid M. Ablayev , title =. Theor. Comput. Sci. , volume =

  3. [3]

    Optimal Communication Complexity of Chained Index , booktitle =

    Janani Sundaresan , editor =. Optimal Communication Complexity of Chained Index , booktitle =

  4. [4]

    The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle =

    Moran Feldman and Ashkan Norouzi. The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle =

  5. [5]

    22nd Annual

    Amit Chakrabarti , title =. 22nd Annual

  6. [6]

    Proceedings of the 28th Conference on Computational Complexity,

    Venkatesan Guruswami and Krzysztof Onak , title =. Proceedings of the 28th Conference on Computational Complexity,

  7. [7]

    48th Annual

    Emanuele Viola and Avi Wigderson , title =. 48th Annual

  8. [8]

    On data structures and asymmetric communication complexity , booktitle =

    Peter Bro Miltersen and Noam Nisan and Shmuel Safra and Avi Wigderson , editor =. On data structures and asymmetric communication complexity , booktitle =

  9. [9]

    Polynomial pass lower bounds for graph streaming algorithms , booktitle =

    Sepehr Assadi and Yu Chen and Sanjeev Khanna , editor =. Polynomial pass lower bounds for graph streaming algorithms , booktitle =

  10. [10]

    Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy , booktitle =

    Sepehr Assadi and Prantar Ghosh and Bruno Loff and Parth Mittal and Sagnik Mukhopadhyay , editor =. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy , booktitle =

  11. [11]

    A new proof of the graph removal lemma , urldate =

    Jacob Fox , journal =. A new proof of the graph removal lemma , urldate =

  12. [12]

    Ravi Kumar and Benjamin Moseley and Sergei Vassilvitskii and Andrea Vattani , title =. 25th

  13. [13]

    Silvio Lattanzi and Benjamin Moseley and Siddharth Suri and Sergei Vassilvitskii , title =

  14. [14]

    Woodruff , editor =

    Akshay Kamath and Eric Price and David P. Woodruff , editor =. A Simple Proof of a New Set Disjointness with Applications to Data Streams , booktitle =

  15. [15]

    Streaming and Communication Complexity of Clique Approximation , booktitle =

    Magn. Streaming and Communication Complexity of Clique Approximation , booktitle =

  16. [16]

    Combinatorics, Probability and Computing , volume=

    Short proofs of some extremal results , author=. Combinatorics, Probability and Computing , volume=. 2014 , publisher=

    2014

  17. [17]

    Woodruff and Peng Ye and Hanlin Zhu , editor =

    Cyrus Rashtchian and David P. Woodruff and Peng Ye and Hanlin Zhu , editor =. Average-Case Communication Complexity of Statistical Problems , booktitle =

  18. [18]

    and Oveis, Shayan Gharan and Trevisan, Luca , TITLE =

    Noga Alon and Ankur Moitra and Benny Sudakov , editor =. Nearly complete graphs decomposable into large induced matchings and their applications , booktitle =. 2012 , url =. doi:10.1145/2213977.2214074 , timestamp =

    work page doi:10.1145/2213977.2214074 2012

  19. [19]

    Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer

    Sepehr Assadi and Sanjeev Khanna and Peter Kiss , editor =. Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer. Proceedings of the 2025 Annual. 2025 , url =. doi:10.1137/1.9781611978322.96 , timestamp =

    work page doi:10.1137/1.9781611978322.96 2025

  20. [20]

    Soheil Behnezhad and Alma Ghafari , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00027 , timestamp =

    work page doi:10.1109/focs61266.2024.00027 2024

  21. [21]

    and Nirkhe, Chinmay , title =

    Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li , editor =. On Regularity Lemma and Barriers in Streaming and Dynamic Matching , booktitle =. 2023 , url =. doi:10.1145/3564246.3585110 , timestamp =

    work page doi:10.1145/3564246.3585110 2023

  22. [22]

    Information Lower Bounds via Self-reducibility

    Braverman, Mark and Garg, Ankit and Pankratov, Denis and Weinstein, Omri. Information Lower Bounds via Self-reducibility. Computer Science -- Theory and Applications. 2013

    2013

  23. [23]

    Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms , booktitle =

    Sepehr Assadi and Ran Raz , editor =. Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms , booktitle =

  24. [24]

    Sepehr Assadi and Janani Sundaresan , title =. 64th

  25. [25]

    Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams , booktitle =

    Jacques Dark and Christian Konrad , editor =. Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams , booktitle =

  26. [26]

    Maximum Matching in Turnstile Streams , booktitle =

    Christian Konrad , editor =. Maximum Matching in Turnstile Streams , booktitle =

  27. [27]

    Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model , booktitle =

    Sepehr Assadi and Sanjeev Khanna and Yang Li and Grigory Yaroslavtsev , editor =. Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model , booktitle =

  28. [28]

    Woodruff , editor =

    Omri Weinstein and David P. Woodruff , editor =. The Simultaneous Communication of Disjointness with Applications to Data Streams , booktitle =

  29. [29]

    Robust lower bounds for communication and stream computation , booktitle =

    Amit Chakrabarti and Graham Cormode and Andrew McGregor , editor =. Robust lower bounds for communication and stream computation , booktitle =

  30. [30]

    Separations and equivalences between turnstile streaming and linear sketching , booktitle =

    John Kallaugher and Eric Price , editor =. Separations and equivalences between turnstile streaming and linear sketching , booktitle =

  31. [31]

    Combinatorics (Keszthely, 1976), Coll

    Triple systems with no six points carrying three triangles , author=. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai , volume=

    1976

  32. [32]

    Woodruff , editor =

    Yuqing Ai and Wei Hu and Yi Li and David P. Woodruff , editor =. New Characterizations in Turnstile Streams with Applications , booktitle =

  33. [33]

    Nguyen and David P

    Yi Li and Huy L. Nguyen and David P. Woodruff , editor =. Turnstile streaming algorithms might as well be linear sketches , booktitle =

  34. [34]

    Bulletin of the London Mathematical Society , volume=

    On graphs decomposable into induced matchings of linear sizes , author=. Bulletin of the London Mathematical Society , volume=. 2017 , publisher=

    2017

  35. [35]

    42nd Annual Symposium on Foundations of Computer Science,

    Noga Alon , title =. 42nd Annual Symposium on Foundations of Computer Science,

  36. [36]

    The 4/3 additive spanner exponent is tight , booktitle =

    Amir Abboud and Greg Bodwin , editor =. The 4/3 additive spanner exponent is tight , booktitle =

  37. [37]

    Naidu and Janani Sundaresan , editor =

    Sepehr Assadi and Christian Konrad and Kheeran K. Naidu and Janani Sundaresan , editor =. O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set , booktitle =

  38. [38]

    Improved Approximation Algorithms for (1, 2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model , booktitle =

    Sharareh Alipour and Ermiya Farokhnejad and Tobias M. Improved Approximation Algorithms for (1, 2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model , booktitle =

  39. [39]

    Streaming Facility Location in High Dimension via Geometric Hashing , booktitle =

    Artur Czumaj and Shaofeng H. Streaming Facility Location in High Dimension via Geometric Hashing , booktitle =

  40. [40]

    Streaming Algorithms for Geometric Steiner Forest , booktitle =

    Artur Czumaj and Shaofeng H. Streaming Algorithms for Geometric Steiner Forest , booktitle =

  41. [41]

    Sublinear Algorithms and Lower Bounds for Estimating

    Yu Chen and Sanjeev Khanna and Zihan Tan , editor =. Sublinear Algorithms and Lower Bounds for Estimating. 50th International Colloquium on Automata, Languages, and Programming,

  42. [42]

    Demaine and Piotr Indyk and Sepideh Mahabadi and Ali Vakilian , editor =

    Erik D. Demaine and Piotr Indyk and Sepideh Mahabadi and Ali Vakilian , editor =. On Streaming and Communication Complexity of the Set Cover Problem , booktitle =

  43. [43]

    Sketching Approximability of All Finite CSPs , journal =

    Chi. Sketching Approximability of All Finite CSPs , journal =

  44. [44]

    Saxena and Noah Singer and Madhu Sudan and Santhoshini Velusamy , editor =

    Raghuvansh R. Saxena and Noah Singer and Madhu Sudan and Santhoshini Velusamy , editor =. Streaming complexity of CSPs with randomly ordered constraints , booktitle =

  45. [45]

    Linear space streaming lower bounds for approximating CSPs , booktitle =

    Chi. Linear space streaming lower bounds for approximating CSPs , booktitle =

  46. [46]

    Streaming Approximation Resistance of Every Ordering

    Noah Singer and Madhu Sudan and Santhoshini Velusamy , editor =. Streaming Approximation Resistance of Every Ordering. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,

  47. [47]

    Approximability of all finite CSPs with linear sketches , booktitle =

    Chi. Approximability of all finite CSPs with linear sketches , booktitle =

  48. [48]

    Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat , booktitle =

    Chi. Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat , booktitle =

  49. [49]

    Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph , booktitle =

    Venkatesan Guruswami and Ameya Velingker and Santhoshini Velusamy , editor =. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph , booktitle =

  50. [50]

    Vu , title =

    Andrew McGregor and Hoa T. Vu , title =. Theory Comput. Syst. , volume =

  51. [51]

    Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams , booktitle =

    Amit Chakrabarti and Andrew McGregor and Anthony Wirth , editor =. Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams , booktitle =

  52. [52]

    Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem , booktitle =

    Sepehr Assadi and Sanjeev Khanna , editor =. Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem , booktitle =

  53. [53]

    Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem , booktitle =

    Sepehr Assadi , editor =. Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem , booktitle =

  54. [54]

    Tight bounds for single-pass streaming complexity of the set cover problem , booktitle =

    Sepehr Assadi and Sanjeev Khanna and Yang Li , editor =. Tight bounds for single-pass streaming complexity of the set cover problem , booktitle =

  55. [55]

    Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model , booktitle =

    Piotr Indyk and Ali Vakilian , editor =. Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model , booktitle =

  56. [56]

    Towards Tight Bounds for the Streaming Set Cover Problem , booktitle =

    Sariel Har. Towards Tight Bounds for the Streaming Set Cover Problem , booktitle =

  57. [57]

    Constructing Long Paths in Graph Streams , booktitle =

    Christian Konrad and Chhaya Trehan , editor =. Constructing Long Paths in Graph Streams , booktitle =

  58. [58]

    Better Coloring of 3-Colorable Graphs , booktitle =

    Ken. Better Coloring of 3-Colorable Graphs , booktitle =

  59. [59]

    Coloring 3-Colorable Graphs with Less than

    Ken. Coloring 3-Colorable Graphs with Less than. J

  60. [60]

    Andrew McGregor , title =

  61. [61]

    On Estimating Maximum Matching Size in Graph Streams , booktitle =

    Sepehr Assadi and Sanjeev Khanna and Yang Li , editor =. On Estimating Maximum Matching Size in Graph Streams , booktitle =

  62. [62]

    On the communication and streaming complexity of maximum bipartite matching , booktitle =

    Ashish Goel and Michael Kapralov and Sanjeev Khanna , editor =. On the communication and streaming complexity of maximum bipartite matching , booktitle =

  63. [63]

    Better bounds for matchings in the streaming model , booktitle =

    Michael Kapralov , editor =. Better bounds for matchings in the streaming model , booktitle =

  64. [64]

    Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model , booktitle =

    Michael Kapralov , editor =. Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model , booktitle =

  65. [65]

    Krokhin and Jakub Oprsal and Marcin Wrochna and Stanislav Zivn

    Andrei A. Krokhin and Jakub Oprsal and Marcin Wrochna and Stanislav Zivn. Topology and Adjunction in Promise Constraint Satisfaction , journal =

  66. [66]

    Monotonicity testing over general poset domains , booktitle =

    Eldar Fischer and Eric Lehman and Ilan Newman and Sofya Raskhodnikova and Ronitt Rubinfeld and Alex Samorodnitsky , editor =. Monotonicity testing over general poset domains , booktitle =

  67. [67]

    New Hardness Results for Graph and Hypergraph Colorings , booktitle =

    Joshua Brakensiek and Venkatesan Guruswami , editor =. New Hardness Results for Graph and Hypergraph Colorings , booktitle =

  68. [68]

    Improved Hardness of Approximating Chromatic Number , booktitle =

    Sangxia Huang , editor =. Improved Hardness of Approximating Chromatic Number , booktitle =

  69. [69]

    42nd Annual Symposium on Foundations of Computer Science,

    Subhash Khot , title =. 42nd Annual Symposium on Foundations of Computer Science,

  70. [70]

    Improved Hardness Results for Approximating the Chromatic Number , booktitle =

    Martin F. Improved Hardness Results for Approximating the Chromatic Number , booktitle =

  71. [71]

    Conditional hardness for approximate coloring , booktitle =

    Irit Dinur and Elchanan Mossel and Oded Regev , editor =. Conditional hardness for approximate coloring , booktitle =

  72. [72]

    Venkatesan Guruswami and Sanjeev Khanna , title =

  73. [73]

    Sanjeev Khanna and Nathan Linial and Shmuel Safra , title =. Comb. , volume =

  74. [74]

    Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! , booktitle =

    Anup Bhattacharya and Arijit Bishnu and Gopinath Mishra and Anannya Upasana , editor =. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! , booktitle =

  75. [75]

    Part II: Reducibility , author=

    Every planar map is four colorable. Part II: Reducibility , author=. Illinois Journal of Mathematics , volume=. 1977 , publisher=

    1977

  76. [76]

    Part I: Discharging , author=

    Every planar map is four colorable. Part I: Discharging , author=. Illinois Journal of Mathematics , volume=. 1976 , publisher=

    1976

  77. [77]

    2025 , note =

    Randomized Algorithms course (CS761) at. 2025 , note =

    2025

  78. [78]

    2024 , note =

    Advanced Algorithms course (CS466) at. 2024 , note =

    2024

  79. [79]

    2024 , note =

    Sublinear Time Algorithms course (6.5240) at. 2024 , note =

    2024

  80. [80]

    CoRR , volume =

    Jackson Morris and Fang Song , title =. CoRR , volume =

Showing first 80 references.