List Colouring Trees in Logarithmic Space
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.
READ FULL TEXT