On the L(h,k)-Labeling of Co-Comparability Graphs
Given two non negative integers h and k, an
L(h,k)-labeling of a graph G=(V,E) is a map from
V to a set of 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 though, in this paper we
deal with co-comparability graphs and two of its subclasses: interval graphs and
unit-interval graphs. Specifically, we provide, in a constructive way,
the first upper bounds on the
L(h,k)-number of co-comparability graphs and interval graphs.
To the best of our knowledge, ours is the first reported result
concerning the L(h,k)-labeling of co-comparability
graphs.
In the special case where k=1, our result improves on
the best previously-known approximation ratio for interval graphs.
Conference Version
Journal Version