@article {IOPORT.02021229,
    author       = {McDiarmid, Colin and Reed, Bruce},
    title        = {Channel assignment on graphs of bounded treewidth.},
    year         = {2003},
    journal      = {Discrete Mathematics},
    volume       = {273},
    number       = {1-3},
    issn         = {0012-365X},
    pages        = {183-192},
    publisher    = {Elsevier Science B.V. (North-Holland), Amsterdam},
    doi          = {10.1016/S0012-365X(03)00236-X},
    abstract     = {Summary: 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,\dots ,B$ such that $|\phi(x)-\phi(y)|\geqslant 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.},
    msc2010      = {G.2.2},
    identifier   = {02021229},
}