本講演はグラフの彩色問題に対する位相幾何学的手法の研究の紹介を行う。グラフに対して様々な単体複体を対応させ、その位相的不変量が彩色数と関係することを調べていく研究分野である。

Lovasz はこのような手法をはじめて導入し、それにより Kneser グラフというグラフの彩色数を決定した。

このような手法は Hom 複体 Hom(T, G)というグラフの組(T, G)に対して定義される単体複体の理論に拡張される。グラフ T がホモトピーテストグラフであるとは、任意のグラフ G に対して Hom(T, G) の連結度と G の彩色数との間に、ある種の不等式が成立することをいう。これは Kozlov により提示された概念で、「いかなるグラフ T がホモトピーテストグラフであるか？」という素朴な問題を核にして、本研究分野は発展してきた。

最後に Wrochna による乗法的グラフへの本研究分野の応用について述べたい。