# Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

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 pathwidt at most $$p$$ require $$(3+\delta)^p\text{poly}(n)$$ time for some $$\delta > 0$$) known for $$k$$-coloring parameterized by pathwidth?

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}$$.