組合せ論セミナー

 


第23回 2012年5月22日 14:00〜15:30

小関健太 (国立情報学研究所)「Claw-free グラフのハミルトン性とそれに関連する予想」


グラフのハミルトン性に関わる予想はいろいろなものが知られているが,その中でも1984 年の Matthews と Sumner の「任意の 4-連結 claw-free グラフはハミルトン閉路を持つ」というものは,他の様々な話題との関連という意味で,有名かつ重要なものとなっている.特にこの予想は,1986 年の Thomassen の「任意の 4-連結 line グラフはハミルトン閉路を持つ」という予想をはじめ,いくつもの予想と同値であることが知られており,本講演ではそれらの予想とその同値性を示す方法を紹介する.