グラフ彩色と無線通信におけるチャネル割当の関連について

摘要

無線通信におけるチャネル割当とグラフ理論における彩色問題は古くから関連性が示され，様々な研究がなされてきた.その中で多くの理論的な研究は，割当てるチャネル数を最小としたものである.これは，彩色問題における染色数に対応するからであり，グラフ理論における結果も応用可能であることからである.ただし，チャネル数を最小にするためには，すべてのすでに割当てられているチャネルを再割当する等，実際に適用するには問題が多い.筆者らは以前の報告において最悪の場合について考察したが，ランダムに終了する通信を考慮したものではなかった.そこで本報告では，この点も考慮し，新たなグラフ彩色問題を提案し，いくつかの結果を示す.