On the complexity of Bandwidth Minimization The graph bandwidth problem is defined as follows. Given a graph $G=(V,E)$, a layout $f$ of $G$ is a one-to-one mapping of the vertices of $G$ onto the integers $\{1, \ldots, |V|\}$. The bandwidth of $f$ is defined as 

$bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} \in E\}$. 

The bandwidth of $G$, denoted $bw(G)$, is defined as the minimum bandwidth of a layout, the minimum being taken over all possible layouts. 

The decision question is: given a graph $G$ and an integer $k$, is $bw(G) \le k$? 

This problem is known to be NP-complete even for trees of maximum degree three [Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978]. The authors show that one can test whether a graph has bandwidth at most two in polynomial time. The case $bw \le 3$ was open. 

Is the complexity of the case $bw \le 3$ known? What do we know about the complexity of the problem when $k$ is not part of the input but a fixed constant at least $4$? 

References would be nice.
The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper.

On the other hand, it is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k)n^{k+1})$ time. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe.