  Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a
bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v
\} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-complete
problem, known to remain NP-complete even on very restricted classes of graphs,
such as trees of maximum degree 3 and caterpillars of hair length 3. In the
realm of parameterized complexity, these results imply that the problem remains
NP-hard on graphs of bounded pathwidth, while it is additionally known to be
W[1]-hard when parameterized by the treedepth of the input graph. In contrast,
the problem does become FPT when parameterized by the vertex cover number of
the input graph. In this paper, we make progress towards the parameterized
(in)tractability of Bandwidth. We first show that it is FPT when parameterized
by the cluster vertex deletion number cvd plus the clique number $\omega$ of
the input graph, thus generalizing the previously mentioned result for vertex
cover. On the other hand, we show that Bandwidth is W[1]-hard when
parameterized only by cvd. Our results generalize some of the previous results
and narrow some of the complexity gaps.
