---
_id: '11825'
abstract:
- lang: eng
  text: We give a fully dynamic (Las-Vegas style) algorithm with constant expected
    amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph
    with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm
    by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning
    random ranks to vertices and does not need to maintain a hierarchical graph decomposition.
    We show that our result does not only have optimal running time, but is also optimal
    in the sense that already deciding whether a Δ-coloring exists in a dynamically
    changing graph with maximum degree at most Δ takes Ω(log n) time per operation.
alternative_title:
- LIPIcs
article_number: '53'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Pan
  full_name: Peng, Pan
  last_name: Peng
citation:
  ama: 'Henzinger MH, Peng P. Constant-time dynamic (Δ+1)-coloring. In: <i>37th International
    Symposium on Theoretical Aspects of Computer Science</i>. Vol 154. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2020.53">10.4230/LIPIcs.STACS.2020.53</a>'
  apa: 'Henzinger, M. H., &#38; Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring.
    In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>
    (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.STACS.2020.53">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>'
  chicago: Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.”
    In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>,
    Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.STACS.2020.53">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>.
  ieee: M. H. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in <i>37th
    International Symposium on Theoretical Aspects of Computer Science</i>, Montpellier,
    France, 2020, vol. 154.
  ista: 'Henzinger MH, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International
    Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
    Aspects of Computer Science, LIPIcs, vol. 154, 53.'
  mla: Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.”
    <i>37th International Symposium on Theoretical Aspects of Computer Science</i>,
    vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a
    href="https://doi.org/10.4230/LIPIcs.STACS.2020.53">10.4230/LIPIcs.STACS.2020.53</a>.
  short: M.H. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical
    Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020.
conference:
  end_date: 2020-03-13
  location: Montpellier, France
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2020-03-10
date_created: 2022-08-12T07:53:05Z
date_published: 2020-03-04T00:00:00Z
date_updated: 2023-02-14T10:03:43Z
day: '04'
doi: 10.4230/LIPIcs.STACS.2020.53
extern: '1'
external_id:
  arxiv:
  - '1907.04745'
intvolume: '       154'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.STACS.2020.53
month: '03'
oa: 1
oa_version: Published Version
publication: 37th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - '9783959771405'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constant-time dynamic (Δ+1)-coloring
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 154
year: '2020'
...