Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

Question

Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two adjacent vertices receive the same color, and at most $k$ distinct colors are used overall.

Assume the input graph $G$ has pathwidth at most $p$. There is a standard argument which showing that the $k$-coloring problem can be solved on such graphs by dynamic programming in $k^p\text{poly}(n)$ time. And this paper of Lokshtanov, Marx, and Saurabh shows that, assuming the Strong Exponential Time Hypothesis, $k$-coloring cannot be solved in $(3-\epsilon)^p\text{poly}(n)$ time or any constant $\epsilon > 0$.

Besides these results, are there any better upper bounds (i.e., algorithms solving $k$-coloring on $n$-node graphs of pathwidth at most $p$ in $(k-\delta)^p\text{poly}(n)$ time) or better lower bounds (i.e., results which state that, assuming some popular conjecture, $k$-coloring on $n$-node graphs of pathwidth at most $p$ require $(3+\delta)^p\text{poly}(n)$ time for some $\delta > 0$) known for $k$-coloring parameterized by pathwidth?

Answer 1

I’m 99% certain that the proof in the paper you cite already shows this - the statement of Theorem 4 states the running time lower bound correctly as $(k-\epsilon)^{fvs}$ and incorrectly as $(3-\epsilon)^{pw}$ — I’m quite sure this is a typo in the theorem statement, and should have been stated as $(k-\epsilon)^{pw}$.

Here is some follow up work on coloring bounded degree and bounded pathwidth graphs: https://arxiv.org/abs/1504.03670

If you bound cutwidth rather than pathwidth, then one can get faster algortihms: https://arxiv.org/abs/1806.10501