In graph theory, a L(h, k)-labelling, L(h, k)-coloring or sometimes L(p, q)-coloring is a (proper) vertex coloring in which every pair of adjacent vertices has color numbers that differ by at least h, and any nodes connected by a 2 length path have their colors differ by at least k.[1] The parameters h, k are understood to be non-negative integers.
The span of an L(h, k)-labelling, ρh,k(G) is the difference between the largest and the smallest assigned frequency.
The goal of the L(h, k)-labelling problem is usually to find a labelling with minimum span.
When h = 1 and k = 0, it is the usual (proper) vertex coloring.
In some variants, the goal is to minimize the number of used colors (the order).