L(h, k)-coloring
{{short description|Type of graph coloring}}
{{DISPLAYTITLE:L(h, k)-coloring}}
In graph theory, a {{math|L(h, k)}}-labelling, {{math|L(h, k)}}-coloring or sometimes {{math|L(p, q)}}-coloring is a (proper) vertex coloring in which every pair of adjacent vertices has color numbers that differ by at least {{mvar|h}}, and any nodes connected by a 2 length path have their colors differ by at least {{mvar|k}}.{{cite book |last1=Chartrand |first1=Gary |last2=Zhang |first2=Ping|author2-link=Ping Zhang (graph theorist) |authorlink1=Gary Chartrand |title=Chromatic Graph Theory |year=2009 |publisher=CRC Press |chapter=14. Colorings, Distance, and Domination |pages=397–438}} The parameters {{math|h, k}} are understood to be non-negative integers.
The problem originated from a channel assignment problem in radio networks. The span of an {{math|L(h, k)}}-labelling, {{math|ρh,k(G)}} is the difference between the largest and the smallest assigned frequency. The goal of the {{math|L(h, k)}}-labelling problem is usually to find a labelling with minimum span.{{citation
| last = Tiziana | first = Calamoneri
| doi = 10.1093/comjnl/bxl018
| issue = 5
| journal = Comput. J.
| mr =
| pages = 585–608
| title = The L(h, k)-Labelling Problem: A Survey and Annotated Bibliography
| volume = 49
| year = 2006}} For a given graph, the minimum span over all possible labelling functions is the {{mvar|λh,k}}-number of {{mvar|G}}, denoted by {{math|λh,k(G)}}.
When {{math|1=h = 1}} and {{math|1=k = 0}}, it is the usual (proper) vertex coloring.
There is a very large number of articles concerning {{math|L(h, k)}}-labelling, with different {{mvar|h}} and {{mvar|k}} parameters and different classes of graphs.
In some variants, the goal is to minimize the number of used colors (the order).