Publication at Faculty of Mathematics and Physics |
2005
Abstract
The paper considers distance constrained labelings of graphs of bounded treewidth. In particular we prove that L(2,1) labeling is NP-hard for series-parallel graphs, i.e., graphs of treewidth two.