DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.16

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Authors: Sepehr Assadi and Helia Yazdanyar

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree Δ can be properly colored with O(Δ/lnΔ) colors, improving upon the "greedy bound" of Δ+1 coloring in general graphs. This coloring can also be found in polynomial time. We present an algorithm for maintaining an O(Δ/lnΔ) 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 Δ^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.

Cite as

Sepehr Assadi and Helia Yazdanyar. Fully Dynamic Algorithms for Coloring Triangle-Free Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2026.16,
  author =	{Assadi, Sepehr and Yazdanyar, Helia},
  title =	{{Fully Dynamic Algorithms for Coloring Triangle-Free Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.16},
  URN =		{urn:nbn:de:0030-drops-264053},
  doi =		{10.4230/LIPIcs.ICALP.2026.16},
  annote =	{Keywords: Dynamic graphs - Graph coloring - Dynamic entropy compression}
}

Search Results

Documents authored by Yazdanyar, Helia

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message