Approximating the L(h, k)-labelling problem
Magnús M. Halldórsson · International Journal of Mobile Network Design and Innovation · 2006
The (h, k)-colouring problem, better known as the L(h, k)-labelling problem, is that of vertex colouring an undirected graph with non-negative integers so that adjacent vertices receive colours that differ by at least h and vertices of distance-2 receive colours that differ by at least k. We give tight bounds on approximations for this problem on general graphs as well as for bipartite, chordal and split graphs.