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?


1 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

  • $\begingroup$ Oh interesting. Looking at the pathwidth bound from Observation 1 in that work of Lokshtanov, Marx, and Saurabh, it seems like you are correct and the statement of Theorem 4 really does just have a typo. $\endgroup$
    – Naysh
    Commented Mar 27, 2022 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.