Monday, May 10, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
The complexity of list-5-colouring H-free graphs

Abstract:

A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\{1, …, k\}$. The list-$k$-colouring problem asks, given $G$ and a $k$-list-assignment $L$, is there a colouring $f$ of $G$ with $f(v)$ in $L(v)$ for all $v$ in $V(G)$? This generalizes the $k$-colouring problem (where we use $L(v) = \{1, …, k\}$ for every vertex).

For $k$ at least $3$, both $k$-colouring and list-$k$-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to $H$-free graphs (for a fixed $H$, excluded as an induced subgraph).

I will present an algorithm for list-$5$-colouring restricted to $H$-free graphs for all $H$ which consist of connected components each of which is a $3$-vertex path. This, together with previous results, gives a complete answer to the question, “for which $H$ is list-$5$-colouring restricted to $H$-free graphs NP-hard?”

Joint work with Sepehr Hajebi and Yanjia Li.