Seminar: Carla Groenland (Utrecht University)

Speaker: Carla Groenland (Utrecht University)


List Colouring Trees in Logspace

Zoom link:
(Meeting ID: 849 0964 5595, Passcode: 772448)


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 of work tape. I will also outline some exciting new parameterized complexity classes that can be described via List Colouring on other classes of graphs (XNLP, XALP, …) via graph width measures (pathwidth, treewidth, …).
This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.