Carla Groenland: List colouring trees in logspace and new parameterized complexity classes

A List Colouring instance consists of a graph and for each vertex v in the graph, a list L(v) of colours that it may be coloured with. I will explain some ideas behind our algorithm that decides whether an n-vertex tree admits a list colouring using O(log n) bits on the work tape. No knowledge of parameterized complexity or graph width measures is expected, but I will also advertise new complexity classes (XNLP, XALP, XSLP) that can be defined using List Colouring (parameterized by pathwidth, treewidth, treedepth respectively).

This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.