第06回セミナー・勉強会
日時: | 2021.02.12 Fri. 15:00-17:00
|
---|---|
会場: | オンライン |
話者: | 小関 健太(横浜国立大学,C01班) |
題目: | 3-正則グラフにおける3-辺彩色のケンペ鎖による遷移 |
概要: | どの隣接2辺も異なる色となるように辺に色を割り当てることをそのグラフの辺彩色といい,特に高々 3 色しか使わないとき 3-辺彩色という.3-辺彩色において,2色で塗られた閉路を1つ選び,その閉路上の色を取り換えることで新しい3-辺彩色が得られる.この操作はケンペによって四色定理の証明のために導入されたもので,現在でも関連問題に対して有力な操作として扱われているものである. 本講演では,3-正則グラフ (どの頂点にも 3本の辺が接続するグラフ) における 3-辺彩色全体の集合に上の遷移を導入し,その到達可能性について議論する.
|
2021.01.29 更新