| 词条 | L(h, k)-coloring |
| 释义 |
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 and k are understood to be non-negative integers. The problem originated from a channel assignment problem in radio networks. 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.[2] For a given graph, the minimum span over all possible labelling functions is the λh,k-number of G, denoted by λh,k(G). When h=1 and k=0, it is the usual (proper) vertex coloring. There is a very large number of articles concerning L(h, k)-labelling, with different h and k parameters and different classes of graphs. In some variants, the goal is to minimize the number of used colors (the order). See also
References1. ^{{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}} 2. ^{{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}} 7 : Computational problems in graph theory|Extensions and generalizations of graphs|Graph theory|Graph coloring|NP-complete problems|NP-hard problems|Radio resource management |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。