Georgia Institute of Technology College of Sciences

The list-$k$-coloring problem is to decide, given a graph $G$ and a list assignment $L$ of $G$ from $V(G)$ to subsets of $\{1,...,k\}$, whether $G$ has a coloring $f$ such that $f(v)$ in $L(v)$ for all $v$ in $V(G)$. The list-$k$-coloring problem is a generalization of the $k$-coloring problem. Thus for $k\geq 3$, both the $k$-coloring problem and the list-$k$-coloring problem are NP-Hard. This motivates studying the complexity of these problems restricted to graphs with a fixed forbidden induced subgraph $H$, which are called $H$-free graphs.

In this talk, I will present a polynomial-time algorithm to solve the list-5-coloring $H$-free graphs with $H$ being the union of $r$ copies of mutually disjoint 3-vertex paths. Together with known results, it gives a complete complexity dichotomy of the list-5-coloring problem restricted to $H$-free graphs. This is joint work with Sepehr Hajebi and Sophie Spirkl.