ホモトピー論の、グラフのクロマティック数の計算への応用

単純グラフGに対し，Gの頂点集合 V(G)から n 点集合への写像であって，辺で結ばれている頂点においては異なる値をとるもののことを，グラフ G の n 彩色という． G の n 彩色が存在するような最小の n を G の彩色数といい、 c(G) で表す．グラフの彩色数を求める問題をグラフの彩色問題という．彩色問題に対してホモトピー論を初めて応用したのは Lovasz の1979年における Kneser 予想の解決である． Lovasz はグラフに対して近傍複体なる単体複体を定義し，その連結度に 3 を足したものが，元のグラフの彩色数の下界を与えることを示し， Kneser グラフの彩色数を決定した．ホム複体とは二つのグラフの組(T,G)に対して定義されるCW複体Hom(T,G)である． T が2-頂点完備グラフ K_2 のとき， Hom(K_2,G) は G の近傍複体 N(G) にホモトピー同値であることが知られている．近傍複体の時と同様， T がホモトピーテストグラフと呼ばれるときには， Hom(T,G) の連結度に c(T) + 1 を足したものが，グラフ G の彩色数を下から抑えることが知られている．ホモトピーテストグラフの例としては，n が 3 以上のときの n-頂点完備グラフ K_n や n-サイクルグラフ C_n などが知られていた．どのようなグラフがホモトピーテストグラフであるかという問題は，この分野の中心的な話題であった．Kozlov は2006年に任意の二部グラフはホモトピーテストグラフであると予想したが，私はこの予想を解決した．また近傍複体が同型であるにも関わらず，彩色数が異なる例を発見した．これは Lovasz が近傍複体の論文において書いた「グラフの彩色数の近傍複体の位相的特徴付けは存在するか」という問いに対する否定的な解答を与える．

単純グラフGに対し，Gの頂点集合 V(G)から n 点集合への写像であって，辺で結ばれている頂点においては異なる値をとるもののことを，グラフ G の n 彩色という． G の n 彩色が存在するような最小の n を G の彩色数といい、 c(G) で表す．グラフの彩色数を求める問題をグラフの彩色問題という．彩色問題に対してホモトピー論を初めて応用したのは Lovasz の1979年における Kneser 予想の解決である． Lovasz はグラフに対して近傍複体なる単体複体を定義し，その連結度に 3 を足したものが，元のグラフの彩色数の下界を与えることを示し， Kneser グラフの彩色数を決定した．ホム複体とは二つのグラフの組(T,G)に対して定義されるCW複体Hom(T,G)である． T が2-頂点完備グラフ K_2 のとき， Hom(K_2,G) は G の近傍複体 N(G) にホモトピー同値であることが知られている．近傍複体の時と同様， T がホモトピーテストグラフと呼ばれるときには， Hom(T,G) の連結度に c(T) + 1 を足したものが，グラフ G の彩色数を下から抑えることが知られている．ホモトピーテストグラフの例としては，n が 3 以上のときの n-頂点完備グラフ K_n や n-サイクルグラフ C_n などが知られていた．どのようなグラフがホモトピーテストグラフであるかという問題は，この分野の中心的な話題であった．Kozlov は2006年に任意の二部グラフはホモトピーテストグラフであると予想したが，私はこの予想を解決した．また近傍複体が同型であるにも関わらず，彩色数が異なる例を発見した．これは Lovasz が近傍複体の論文において書いた「グラフの彩色数の近傍複体の位相的特徴付けは存在するか」という問いに対する否定的な解答を与える．