List Colouring Trees in Logarithmic Space
Publication date
2022-09-01
Authors
Bodlaender, Hans
Groenland, Carla
Jacob, Hugo
Editors
Chechik, Shiri
Navarro, Gonzalo
Rotenberg, Eva
Herman, Grzegorz
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
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.
Keywords
graph algorithms, List colouring, logspace, space complexity, treepartition-width, trees, Software
Citation
Bodlaender, H L, Groenland, C & Jacob, H 2022, List Colouring Trees in Logarithmic Space. in S Chechik, G Navarro, E Rotenberg & G Herman (eds), 30th Annual European Symposium on Algorithms, ESA 2022. Leibniz International Proceedings in Informatics, LIPIcs, vol. 244, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 24:1-24:15, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, 5/09/22. https://doi.org/10.4230/LIPIcs.ESA.2022.24, conference