Constant-time dynamic (+1)-coloring

DOI10.4230/LIPICS.STACS.2020.53MaRDI QIDQ5874328zbMATH OpenFDO

Authors Pan Peng, Monika R. Henzinger

Publication date 7 February 2023

zbMATH Keywords

graph coloringrandom samplingdynamic graph algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Constant-time Dynamic (Δ +1)-Coloring
• Fully Dynamic (Δ +1)-Coloring in O (1) Update Time
• scientific article; zbMATH DE number 6850309
• Dynamic graph coloring
• Dynamic graph coloring

Cited in

(5)

• Constant-time Dynamic (Δ +1)-Coloring
• Fully Dynamic (Δ +1)-Coloring in O (1) Update Time
• Constant-time dynamic weight approximation for minimum spanning forest
• Improved dynamic colouring of sparse graphs
• Trade-offs in dynamic coloring for bipartite and general graphs

This page was built for publication: Constant-time dynamic \((\Delta+1)\)-coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874328)