Channel assignment on graphs of bounded treewidth

The following 'constraint matrix span problem' arises in the assignment of radio channels in cellular communications systems. Given a graph G with a positive integer length l(xy) for each edge xy, and given a positive integer B, can we assign to each vertex x a channel phi(x) from 1,...,B such that \phi(x) - phi(y)\ greater than or equal to l(xy) for each edge xy? We show that this problem is NP-complete for graphs of treewidth at most 3, but there is a fully polynomial time approximation scheme for the problem on graphs of bounded treewidth. We see also that it is NP-complete for graphs which can be made bipartite by deleting a single vertex. (C) 2003 Elsevier B.V. All rights reserved.