In graph theory, a -labelling, -coloring or sometimes -coloring is a (proper) vertex coloring in which every pair of adjacent vertices has color numbers that differ by at least, and any nodes connected by a 2 length path have their colors differ by at least .[1] The parameters are understood to be non-negative integers.
The problem originated from a channel assignment problem in radio networks. The span of an -labelling, is the difference between the largest and the smallest assigned frequency. The goal of the -labelling problem is usually to find a labelling with minimum span. For a given graph, the minimum span over all possible labelling functions is the -number of, denoted by .
When and, it is the usual (proper) vertex coloring.
There is a very large number of articles concerning -labelling, with different and parameters and different classes of graphs.
In some variants, the goal is to minimize the number of used colors (the order).