---
res:
  bibo_abstract:
  - 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Pan
      foaf_name: Peng, Pan
      foaf_surname: Peng
  bibo_doi: 10.4230/LIPIcs.STACS.2020.53
  bibo_volume: 154
  dct_date: 2020^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959771405
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Constant-time dynamic (Δ+1)-coloring@
...
