L(h,k) colorazione di grafi con particolari ordinamenti lineari nell'insieme dei nodi

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.( "On the L(h,k)-Labeling of Co-Comparability Graphs", Proc. of IntErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE '07), Lecture Notes in computer Science 4614, pp. 116-127, 2007 and "On the L(h,k)-Labeling of Co-Comparability Graphs ", Networks, 53(1); p. 27-34, 2009)