2022/06/20 by Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2206.09750
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.