セミナー

談話会

タイトル	イマージョンを含まないグラフに対する彩色アルゴリズム
開催日時	2017年6月23日 17:45-18:45
主催者
講演者	垣村 尚徳 氏（慶應義塾大学）
場所	慶應義塾大学　矢上キャンパス 14棟631A/B
内容	グラフの彩色問題とは隣り合う頂点が異なる色を持つように頂点を塗る問題であり，グラフ理論における基本的な問題である． 彩色問題に関する有名な結果として，グラフが平面的ならば4色で彩色できること（4色定理）が知られている． 4色定理の一般化であるHadwiger予想は，k頂点のクリークK_kをマイナーとして含まないグラフは(k-1)色で彩色できるという予想であり，グラフ理論における重要な未解決問題のひとつである． 本研究では，マイナーと似た概念であるイマージョンという関係を考え，イマージョンを含まないグラフを効率的に彩色するアルゴリズムを提案する． 本研究は河原林健一氏(国立情報学研究所)との共同研究である．
資料
URL