L(h, K)-coloring
   HOME

TheInfoList



OR:

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