Improved Dynamic Colouring of Sparse Graphs

Aleksander B. G. Christiansen, Krzysztof Nowicki, Eva Rotenberg

Type: Preprint

Publication Date: 2022-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.2211.06858

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Improved Dynamic Colouring of Sparse Graphs	2023	Aleksander B. G. Christiansen Krzysztof Nowicki Eva Rotenberg
+	Sparsity-Parameterised Dynamic Edge Colouring	2023	Aleksander B. J. Christiansen Eva Rotenberg Juliette Vlieghe
+ PDF Chat	Deterministic Dynamic Edge-Colouring	2024	Aleksander B. G. Christiansen
+	Fully-dynamic $α+ 2$ Arboricity Decomposition and Implicit Colouring	2022	Aleksander B. G. Christiansen Eva Rotenberg
+ PDF Chat	Dynamic O(arboricity) coloring in polylogarithmic worst-case time	2024	Mohsen Ghaffari Christoph Grunau
+	An Improved Randomized Data Structure for Dynamic Graph Connectivity	2015	Zhengyu Wang
+	Fully Dynamic Effective Resistances	2018	David Durfee Yu Gao Gramoz Goranci Richard Peng
+	Fully Dynamic MIS in Uniformly Sparse Graphs	2018	Krzysztof Onak Baruch Schieber Shay Solomon Nicole Wein
+	Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras	2022	Josh Alman Dean Hirsch
+ PDF Chat	Lower bounds for graph reconstruction with maximal independent set queries	2024	Lukas Michel Alex Scott
+	Efficient fully dynamic elimination forests with applications to detecting long paths and cycles	2020	Jiehua Chen Wojciech Czerwiński Yann Disser Andreas Emil Feldmann Danny Hermelin Wojciech Nadara Michał Pilipczuk Marcin Pilipczuk Manuel Sorge Bartłomiej Wróblewski
+	Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time	2016	Danupon Nanongkai Thatchaphol Saranurak
+	On Dynamic Breadth-First Search in External-Memory	2008	Ulrich Meyer
+	On Dynamic Breadth-First Search in External-Memory	2008	Ulrich Meyer
+ PDF Chat	Efficient fully dynamic elimination forests with applications to detecting long paths and cycles	2021	Jiehua Chen Wojciech Czerwiński Yann Disser Andreas Emil Feldmann Danny Hermelin Wojciech Nadara Marcin Pilipczuk Michał Pilipczuk Manuel Sorge Bartłomiej Wróblewski
+	Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting	2021	Shangqi Lu Yufei Tao
+ PDF Chat	Optimal Decremental Connectivity in Non-Sparse Graphs	2021	Anders Aaman Adam Karczmarz Jakub Łącki Nikos Parotsidis Peter Rasmussen Mikkel Thorup
+	Optimal Decremental Connectivity in Non-Sparse Graphs	2021	Anders Aaman Adam Karczmarz Jakub Łącki Nikos Parotsidis Peter Rasmussen Mikkel Thorup
+	Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-\epsilon})$-Time	2016	Danupon Nanongkai Thatchaphol Saranurak
+	Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity	2020	Monika Henzinger Stefan Neumann Andreas Wiese

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors