Title Distance constrained labeling of precolored trees
Authors Jan Kratochvil, Charles University, Prague
Andrzej Proskurowski, University of Oregon, Eugene
Main Fields 1. analysis of algorithms
4. computational complexity
7. design of algorithms
Other Main Fields
Abstract + Keywords Graph colorings with distance constraints are motivated by the frequency
assignment problem. The so called l(p,q)-labeling problem
for coloring the vertices of a given graph with integers from the range
{0,1,...,l} so that labels of adjacent vertices differ by
least p and labels of vertices at distance 2 differ by at least q,
p,q are fixed integers and integer l is part of the input. It
is known that this problem is NP-complete for general graphs, even
when l is fixed, i.e., not part of the input ,
but polynomially solvable for trees for (p,q)=(2,1).
It was conjectured that the general case is also polynomial for trees.
We consider the precoloring
extension version of the problem (i.e., when some vertices of the input
tree are already precolored) and show that in this setting the
cases q=1 and q>1 behave differently: the problem is polynomial for
q=1 and any p, and it is NP-complete for any p>q>1.

Keywords: graph labeling, distance constraints