組合せとグラフの理論（塩田）2023年度 第11回

　第１回に、地図を塗り分ける「四色問題」のお話をしました。 前回は双対グラフを勉強して、 「面」を塗り分けることは、 双対グラフの「頂点」を塗り分けることに読み替えると処理しやすい、 という話をしました。
　今日はその、頂点の塗り分け ― 専門用語で「点彩色」 ― の勉強をします。

  1. 点彩色・彩色数の定義
  2. 基本的命題
  3. $K_n$ を含まないのに彩色数が $n$ であるグラフ
  4. スケジュール調整問題
  5. 彩色数の上限についての定理
  6. 平面的グラフの場合
  7. 地図の彩色
  8. 注意、今日のまとめと宿題

配布プリント

戻る