The bandwidth problem has a long history and a number of important applications. It is the problem of enumerating the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. We will show for any constant $k\in\nat$ that there is no polynomial time approximation algorithm with an approximation factor of $k$. Furthermore, we will show that this result holds also for caterpillars, a class of restricted trees. We construct for any $x,\epsilon\in\rel$ with $x>1$ and $\epsilon>0$ a graph class for which an approximation algorithm with an approximation factor of $x+\epsilon$ exists, but the approximation of the bandwidth problem within a factor of $x-\epsilon$ is NP-complete. The best previously known approximation factors for the intractability of the bandwidth approximation problem were $1.5$ for general graphs and $4/3$ for trees.