L(h, k)-カラーリング

グラフの色分けの種類

グラフ理論において、 $L(h, k)$ -ラベリング、 $L(h, k)$ -カラーリング、または $L(p, q)$ -カラーリングは、隣接する頂点のすべてのペアの色番号が少なくとも $h$ だけ異なり、長さ2のパスによって接続されたすべてのノードの色が少なくとも $kだけ異なるような$ （適切な）頂点カラーリングです。^[1]パラメータ $h$ $、$ $k$ は非負の整数であると理解されています。

この問題は、無線ネットワークにおけるチャネル割り当て問題に端を発する。L $($ $h$ $,$ $k$ $)$ -ラベリングのスパン $ρ$ $h,k$ $($ $G$ $)は、割り当てられた周波数の最大値と最小値の差である。L$ $($ $h$ $,$ $k$ $)$ -ラベリング問題の目標は、通常、スパンが最小となるラベリングを見つけることである。^[2]与えられたグラフにおいて、すべての可能なラベリング関数における最小スパンは、 $Gの$ $λ$ $h,k$ 数であり、 $λ$ $h,k$ $($ $G$ $)$ と表記される。

$h = 1$ かつ $k = 0$ の場合には、通常の（適切な）頂点彩色になります。

異なる $h$ および $k$ パラメータと異なるグラフのクラスを使用した $L(h, k)$ ラベル付けに関する記事は非常に多数あります。

いくつかのバリエーションでは、使用される色の数（順序）を最小限に抑えることが目標となります。

参照

L(2,1)-着色

参考文献

^ Chartrand, Gary ; Zhang, Ping (2009). 「14. 色彩、距離、そして支配」.クロマティックグラフ理論. CRC Press. pp. 397– 438.
^ Tiziana, Calamoneri (2006)、「L(h, k)-ラベリング問題：概説と注釈付き参考文献」、Comput. J.、49 (5): 585– 608、doi :10.1093/comjnl/bxl018

このグラフ理論関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[e01-1] Chartrand, Gary ; Zhang, Ping (2009). 「14. 色彩、距離、そして支配」.クロマティックグラフ理論. CRC Press. pp. 397– 438.

[Tiziana-2] Tiziana, Calamoneri (2006)、「L(h, k)-ラベリング問題：概説と注釈付き参考文献」、Comput. J.、49 (5): 585– 608、doi :10.1093/comjnl/bxl018