ラジオカラーリング

数学の一分野であるグラフ理論において、無向グラフの無線彩色は、隣接する頂点のラベルが少なくとも 2 異なり、互いに距離 2 にある頂点のラベルが少なくとも 1 異なるように、グラフに正の整数ラベルを割り当てるグラフ彩色の形式です。無線彩色は、Griggs と Yeh (1992) によって、 $L$ $(2,1)$ -ラベリングという別名で最初に研究されました。^[1]^[2]これは、フランク・ハラリーによって無線彩色と呼ばれました。これは、グラフと割り当てられたチャネル周波数の両方で互いに近くにあるラジオ局間の電磁干渉を回避しながら、ラジオ放送のチャネル割り当ての問題をモデル化するためです。

ラジオカラーリングの範囲は最大のラベルであり、グラフのラジオカラーリング番号はラジオカラーリングの最小の範囲です。 ^[1]たとえば、1つの辺を持つ2つの頂点からなるグラフのラジオカラーリング番号は3です。これは、1つの頂点にラベル1、もう1つの頂点にラベル3が付いたラジオカラーリングですが、このグラフのラジオカラーリングでラベル1とラベル2のみを使用することはできません。

計算の複雑さ

与えられた（または最小の）スパンを持つラジオカラーリングを見つけることは、平面グラフ、分割グラフ、または二部グラフの補グラフに制限されている場合でも、NP完全です。^[1]^[3]しかし、木とコグラフの場合は多項式時間で解くことができます。^[1]^{[4]任意のグラフの場合は、}単指数時間で解くことができ、すべての可能なカラーリングを力ずくで探すよりも大幅に高速です。^[5]^[6]

その他のプロパティ

$n$ 頂点グラフの無線彩色数は1 から $2 n - 1$ までの範囲であるが、ほとんどすべての $n$ 頂点グラフの無線彩色数はちょうど $n$ である。これは、これらのグラフの直径がほぼ常に少なくとも 2 である（すべての頂点が異なる色を持つことが強制され、無線彩色数が少なくとも $nになることが強制される）が、$ 補グラフにハミルトン経路がほぼ常に存在するためである。この経路の連続する頂点には連続した色を割り当てることができるため、無線彩色で数字を飛ばさずに済む。^[7]

参考文献

^ abcd Broersma, Hajo (2005)、「色付け問題の一般的な枠組み: 古い結果、新しい結果、未解決の問題」(PDF)、組み合わせ幾何学とグラフ理論(PDF)、Lecture Notes in Comput. Sci.、vol. 3330、Springer、ベルリン、pp. 65–79、doi :10.1007/978-3-540-30540-8_7、ISBN 978-3-540-24401-1、MR 2172960特にセクション 3「ラジオの色付け」を参照してください。
^ グリッグス、ジェロルド R.; イェー、ロジャー K. (1992)、「距離 2 の条件によるグラフのラベル付け」、SIAM 離散数学ジャーナル、5 (4): 586–595、doi :10.1137/0405048、MR 1186826。
^ Bodlaender, Hans L. ; Kloks, Ton; Tan, Richard B.; van Leeuwen, Jan (2000)、「グラフの $λ色付け」、$ STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science、リール、フランス、2000 年 2 月 17 ～ 19 日、議事録、Lecture Notes in Computer Science、vol. 1770、Springer、ベルリン、pp. 395 ～ 406、doi :10.1007/3-540-46541-3_33、ISBN 978-3-540-67141-1、MR 1781749。
^ Chang, Gerard J.; Kuo, David (1996)、「グラフ上の $L$ $(2,1)$ ラベル付け問題」、SIAM Journal on Discrete Mathematics、9 (2): 309–316、CiteSeerX 10.1.1.51.2004、doi :10.1137/S0895480193245339、MR 1386886 。
^ ハヴェ、フレデリック;クラザー、マーティン。Kratochvíl, 1月;クラッチュ、ディーター。 Liedloff、Mathieu (2011)、「グラフの L(2,1)-ラベル付けのための正確なアルゴリズム」(PDF)、Algorithmica、59 (2): 169–194、doi :10.1007/s00453-009-9302-7、MR 2765572、S2CID 2634447。
^ Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011)、「グラフのL(2,1)ラベル付けの正確なアルゴリズムの複雑さについて」、Information Processing Letters、111 (14): 697–701、doi :10.1016/j.ipl.2011.04.010、MR 2840535。
^ Harary, Frank ; Plantholt, Michael (1999)、「ラジオカラーリング数がノードの数に等しいグラフ」、Graph colouring and applications (Montréal, QC, 1997)、CRM Proc. Lecture Notes、vol. 23、Providence, RI: American Mathematical Society、pp. 99–100、MR 1723637。

[broersma-1] Broersma, Hajo (2005)、「色付け問題の一般的な枠組み: 古い結果、新しい結果、未解決の問題」(PDF)、組み合わせ幾何学とグラフ理論(PDF)、Lecture Notes in Comput. Sci.、vol. 3330、Springer、ベルリン、pp. 65–79、doi :10.1007/978-3-540-30540-8_7、ISBN 978-3-540-24401-1、MR 2172960特にセクション 3「ラジオの色付け」を参照してください。

[2] グリッグス、ジェロルド R.; イェー、ロジャー K. (1992)、「距離 2 の条件によるグラフのラベル付け」、SIAM 離散数学ジャーナル、5 (4): 586–595、doi :10.1137/0405048、MR 1186826。

[3] Bodlaender, Hans L. ; Kloks, Ton; Tan, Richard B.; van Leeuwen, Jan (2000)、「グラフの $λ色付け」、$ STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science、リール、フランス、2000 年 2 月 17 ～ 19 日、議事録、Lecture Notes in Computer Science、vol. 1770、Springer、ベルリン、pp. 395 ～ 406、doi :10.1007/3-540-46541-3_33、ISBN 978-3-540-67141-1、MR 1781749。

[4] Chang, Gerard J.; Kuo, David (1996)、「グラフ上の $L$ $(2,1)$ ラベル付け問題」、SIAM Journal on Discrete Mathematics、9 (2): 309–316、CiteSeerX 10.1.1.51.2004、doi :10.1137/S0895480193245339、MR 1386886 。

[5] ハヴェ、フレデリック;クラザー、マーティン。Kratochvíl, 1月;クラッチュ、ディーター。 Liedloff、Mathieu (2011)、「グラフの L(2,1)-ラベル付けのための正確なアルゴリズム」(PDF)、Algorithmica、59 (2): 169–194、doi :10.1007/s00453-009-9302-7、MR 2765572、S2CID 2634447。

[6] Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011)、「グラフのL(2,1)ラベル付けの正確なアルゴリズムの複雑さについて」、Information Processing Letters、111 (14): 697–701、doi :10.1016/j.ipl.2011.04.010、MR 2840535。

[7] Harary, Frank ; Plantholt, Michael (1999)、「ラジオカラーリング数がノードの数に等しいグラフ」、Graph colouring and applications (Montréal, QC, 1997)、CRM Proc. Lecture Notes、vol. 23、Providence, RI: American Mathematical Society、pp. 99–100、MR 1723637。