<p>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 <span class="math-container">$(k-\epsilon)^{fvs}$</span> and incorrectly as <span class="math-container">$(3-\epsilon)^{pw}$</span> — I’m quite sure this is a typo in the theorem statement, and should have been stated as <span class="math-container">$(k-\epsilon)^{pw}$</span>.</p>
<p>Here is some follow up work on coloring bounded degree and bounded pathwidth graphs:  <a href="https://arxiv.org/abs/1504.03670" rel="nofollow noreferrer">https://arxiv.org/abs/1504.03670</a></p>
<p>If you bound cutwidth rather than pathwidth, then one can get faster algortihms: <a href="https://arxiv.org/abs/1806.10501" rel="nofollow noreferrer">https://arxiv.org/abs/1806.10501</a></p>

CC BY-SA 4.0
2022-03-27T23:30:23.490Z
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.
Naysh
CC BY-SA 4.0
2022-03-27T20:06:39.870Z
2022-03-27T20:06:39.870Z
daniello
<p>Let <span class="math-container">$k$</span> be a positive integer. In the <span class="math-container">$k$</span>-coloring problem, we are given a graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> nodes, and want to determine if there is a way to assign a color to each vertex of <span class="math-container">$G$</span> such that no two adjacent vertices receive the same color, and at most <span class="math-container">$k$</span> distinct colors are used overall.</p>
<p>Assume the input graph <span class="math-container">$G$</span> has pathwidth at most <span class="math-container">$p$</span>. There is a standard argument which showing that the <span class="math-container">$k$</span>-coloring problem can be solved on such graphs by dynamic programming in <span class="math-container">$k^p\text{poly}(n)$</span> time. And <a href="https://arxiv.org/abs/1007.5450" rel="nofollow noreferrer">this paper</a> of Lokshtanov, Marx, and Saurabh shows that, assuming the Strong Exponential Time Hypothesis, <span class="math-container">$k$</span>-coloring cannot be solved in <span class="math-container">$(3-\epsilon)^p\text{poly}(n)$</span> time or any constant <span class="math-container">$\epsilon &gt; 0$</span>.</p>
<p>Besides these results, <strong>are there any better upper bounds</strong> (i.e., algorithms solving <span class="math-container">$k$</span>-coloring on <span class="math-container">$n$</span>-node graphs of pathwidth at most <span class="math-container">$p$</span> in <span class="math-container">$(k-\delta)^p\text{poly}(n)$</span> time) <strong>or better lower bounds</strong> (i.e., results which state that, assuming some popular conjecture, <span class="math-container">$k$</span>-coloring on <span class="math-container">$n$</span>-node graphs of pathwidth at most <span class="math-container">$p$</span> require <span class="math-container">$(3+\delta)^p\text{poly}(n)$</span> time for some <span class="math-container">$\delta &gt; 0$</span>) <strong>known for <span class="math-container">$k$</span>-coloring parameterized by pathwidth?</strong></p>

<cc.complexity-theory><ds.algorithms><graph-algorithms><parameterized-complexity><treewidth>
Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)
Naysh
# Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

(Asked by: username_0 on 2022-03-27)

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](https://arxiv.org/abs/1007.5450) 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?**

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, parameterized-complexity, treewidth

---

## 1 answers

### Answer by username_1 on 2022-03-27. Score: 2 | Accepted answer

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>

> **Comments:**
> **username_0**: 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.  

---

