In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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 .
The parameters are understood to be non-negative
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s.
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'').
See also
*
L(2,1)-coloring
References
Graph coloring
Radio resource management
{{graph-stub