サムネイル|6サイクル(スパン-5)の最適無線彩色の一例 無向グラフの無線彩色（むせんさいしょく、）とは、グラフ理論において、隣接する頂点のラベルが少なくとも2離れており、かつ互いに距離2にある頂点のラベルが少なくとも1離れているようにグラフに正整数のラベルを割り当てるグラフ彩色の形式である。無線彩色は、によって-ラベリングという名前で初めて研究された. See in particular Section 3, "Radio coloring"..。後に、フランク・ハラリーによって無線彩色と名付けられたが、これは、周波数が互いに近いラジオ局間の電磁干渉を回避しながら、ラジオ放送のチャンネル割り当ての問題をモデル化するためである。
無線彩色のスパンとは、そのグラフの最大ラベルであり、グラフの無線彩色数とは、無線彩色の最小のスパンである。例えば、1つの辺を持つ2つの頂点からなるグラフの無線彩色数は3である。
計算複雑性 与えられた（もしくは最小の）スパンをもつ無線彩色グラフを見つけることは、平面グラフ、分割グラフ、あるいは2部グラフの補グラフに限定した場合においてもNP完全である.。一方、木や補約可能グラフにおいては、多項式時間で解くことができる.。また、任意のグラフは単指数時間で解くことができ、すべての可能な彩色を力ずくで探索するよりも大幅に高速である..。
その他の特性 頂点グラフの無線彩色数はからまでの範囲であるが、ほとんどすべての 頂点グラフの無線彩色数はちょうどである。これは、ほとんどすべてのグラフは、直径が少なくとも2であり、（すべての頂点は異なる色を持ち、無線彩色数が少なくともであるとする）かつ補グラフにはほとんどの場合、ハミルトン経路が存在するからである。この経路の連続する頂点には連続する色を割り当てることができるため、無線彩色において数字の飛び越しを避けることができる.。
脚注 出典