List Colouring Trees in Logarithmic Space
Conference Paper
(2022)
Author(s)
Hans L. Bodlaender (Universiteit Utrecht)
Carla Groenland (Universiteit Utrecht)
Hugo Jacob (ENS Paris-Saclay)
Affiliation
External organisation
DOI related publication
https://doi.org/10.4230/LIPIcs.ESA.2022.24
To reference this document use:
https://resolver.tudelft.nl/uuid:8e9eab50-4f31-437c-bda9-c6408250afd1
More Info
expand_more
expand_more
Publication Year
2022
Language
English
Affiliation
External organisation
ISBN (electronic)
9783959772471
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.
No files available
Metadata only record. There are no files for this record.