L(h,1)-labeling, h=0, 1, 2, is a class of coloring problems arising from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least h apart while nodes connected by a two long path must receive different colors. This problem is NP-complete even when limited to planar graphs. Here, we focus on L(h,1)-labeling restricted to regular tilings of the plane and to outerplanar graphs. We give a unique parametric algorithm labeling each regular tiling of the plane. For these networks, a channel can be assigned to any node in constant time, provided that relative positions of the node in the network is locally known. Regarding outerplanar graphs with maximum degree Delta, we improve the best known upper bounds from Delta +9, Delta +5 and Delta +3 to Delta + 3, Delta +1 and Delta colors for the values of h equal to 2, 1 and 0, respectively, for sufficiently large values of $\Delta$. For h=0, 1 this result proves the polinomiality of the problem for outerplanar graphs. Finally, we study the special case Delta=3, achieving surprising results.

PDF Files

Journal Version