| 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 asks for coloring the vertices of a given graph with integers from the range {0,1,...,l} so that labels of adjacent vertices differ by at least p and labels of vertices at distance 2 differ by at least q, where 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 |