無線彩色
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/10/10 08:14 UTC 版)
無向グラフの無線彩色（むせんさいしょく、英: Radio coloring）とは、グラフ理論において、隣接する頂点のラベルが少なくとも2離れており、かつ互いに距離2にある頂点のラベルが少なくとも1離れているようにグラフに正整数のラベルを割り当てるグラフ彩色の形式である。無線彩色は、Griggs & Yeh (1992)によってL(2,1)-ラベリングという名前で初めて研究された[1][2]。後に、フランク・ハラリーによって無線彩色と名付けられたが、これは、周波数が互いに近いラジオ局間の電磁干渉を回避しながら、ラジオ放送のチャンネル割り当ての問題をモデル化するためである。
無線彩色のスパンとは、そのグラフの最大ラベルであり、グラフの無線彩色数とは、無線彩色の最小のスパンである[1]。例えば、1つの辺を持つ2つの頂点からなるグラフの無線彩色数は3である。
計算複雑性
与えられた（もしくは最小の）スパンをもつ無線彩色グラフを見つけることは、平面グラフ、分割グラフ、あるいは2部グラフの補グラフに限定した場合においてもNP完全である[1][3]。一方、木や補約可能グラフにおいては、多項式時間で解くことができる[1][4]。また、任意のグラフは単指数時間で解くことができ、すべての可能な彩色を力ずくで探索するよりも大幅に高速である[5][6]。
その他の特性
頂点グラフの無線彩色数はからまでの範囲であるが、ほとんどすべての 頂点グラフの無線彩色数はちょうどである。これは、ほとんどすべてのグラフは、直径が少なくとも2であり、（すべての頂点は異なる色を持ち、無線彩色数が少なくともであるとする）かつ補グラフにはほとんどの場合、ハミルトン経路が存在するからである。この経路の連続する頂点には連続する色を割り当てることができるため、無線彩色において数字の飛び越しを避けることができる[7]。
脚注・出典
- ^ a b c d Broersma, Hajo (2005), “A general framework for coloring problems: old results, new results, and open problems”, Combinatorial geometry and graph theory, Lecture Notes in Comput. Sci., 3330, Springer, Berlin, pp. 65–79, doi:10.1007/978-3-540-30540-8_7, ISBN 978-3-540-24401-1, MR 2172960. See in particular Section 3, "Radio coloring".
- ^ Griggs, Jerrold R.; Yeh, Roger K. (1992), “Labelling graphs with a condition at distance 2”, SIAM Journal on Discrete Mathematics 5 (4): 586–595, doi:10.1137/0405048, MR 1186826.
- ^ Bodlaender, Hans L.; Kloks, Ton; Tan, Richard B.; van Leeuwen, Jan (2000), “λ-coloring of graphs”, STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 17–19, 2000, Proceedings, Lecture Notes in Computer Science, 1770, Springer, Berlin, 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), “The L(2,1)-labeling problem on graphs”, SIAM Journal on Discrete Mathematics 9 (2): 309–316, doi:10.1137/S0895480193245339, MR 1386886.
- ^ Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu (2011), “Exact algorithms for L(2,1)-labeling of graphs”, Algorithmica 59 (2): 169–194, doi:10.1007/s00453-009-9302-7, MR 2765572.
- ^ Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011), “On the complexity of exact algorithm for L(2,1)-labeling of graphs”, Information Processing Letters 111 (14): 697–701, doi:10.1016/j.ipl.2011.04.010, MR 2840535.
- ^ Harary, Frank; Plantholt, Michael (1999), “Graphs whose radio coloring number equals the number of nodes”, Graph colouring and applications (Montréal, QC, 1997), CRM Proc. Lecture Notes, 23, Providence, RI: American Mathematical Society, pp. 99–100, MR 1723637.
- 無線彩色のページへのリンク
