On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
Tiziana Calamoneri, Saverio Caminiti, Rossella Petreschi, Stephan Olariu · Networks · 2008
Abstract Given two nonnegative integers h and k, an L(h, k)‐labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)‐labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)‐labeling problem is NP‐complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co‐comparability graphs, its subclass of interval graphs, and circular‐arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)‐labeling of co‐comparability and circular‐arc graphs. In particular, we provide the first algorithm to L(h, k)‐label co‐comparability, interval, and circular‐arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously‐known ones using a number of colors that is at most twice the optimum. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009