Radio coloring とは

グラフ理論では、数学の枝である無向グラフの無線着色は、隣接する頂点のラベルが少なくとも2つ異なるように正の整数ラベルをグラフに割り当て、頂点のラベル互いに距離2のところで少なくとも1つは異なる。ラジオの彩色はGriggs&Yeh(1992)が最初にL(2,1)という別の名前で調べました。それは、ラジオ放送におけるチャンネル割り当ての問題をモデル化し、グラフと割り当てられたチャンネル周波数の両方でお互いに近いラジオ局間の電磁干渉を回避するので、Frank Hararyによるラジオ・カラーリングと呼ばれていました。
ラジオ・カラーリングのスパンはその最大ラベルであり、グラフのラジオ・カラー・ナンバーはラジオ・カラーリングの可能な最小スパンです。たとえば、1つのエッジを持つ2つの頂点で構成されるグラフは、ラジオカラー番号3を持っています.1つの頂点が1、もう1つが3とラベル付けされたラジオカラーリングですが、このグラフのラジオの色付けだけが使用できませんラベル1とラベル2。