Abstract
We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1, . . . , n} of available colours for each v ∈ V , a list colouring for G is a proper colouring c such that c(v) ∈ L(v) for all v.
Original language | English |
---|---|
Title of host publication | 30th Annual European Symposium on Algorithms, ESA 2022 |
Editors | Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Pages | 24:1-24:15 |
Number of pages | 15 |
ISBN (Electronic) | 9783959772471 |
ISBN (Print) | 9783959772471 |
DOIs | |
Publication status | Published - 1 Sept 2022 |
Event | 30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany Duration: 5 Sept 2022 → 9 Sept 2022 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 244 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 30th Annual European Symposium on Algorithms, ESA 2022 |
---|---|
Country/Territory | Germany |
City | Berlin/Potsdam |
Period | 5/09/22 → 9/09/22 |
Bibliographical note
Funding Information:Funding Carla Groenland: Supported by the project CRACKNP that has received funding from the European Research Council (grant agreement No 853234).
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Funding
Funding Carla Groenland: Supported by the project CRACKNP that has received funding from the European Research Council (grant agreement No 853234).
Keywords
- graph algorithms
- List colouring
- logspace
- space complexity
- treepartition-width
- trees