List Colouring Trees in Logarithmic Space

06/20/2022

∙

by   Hans L. Bodlaender, et al.

∙

0

∙

share

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.