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