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

同伦理论在图色数计算中的应用

基本信息

批准号：
13J04699
负责人：
松下尚弘
金额：
$ 1.73万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2013
资助国家：
日本
起止时间：
2013-04-01 至 2016-03-31
项目状态：
已结题

项目摘要

単純グラフ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 年解决了克内泽猜想。 Lovasz 为图定义了一个称为邻域复形的单纯复形，并证明连通性加 3 给出了原始图的色数下界，并确定了 Kneser 图的色数． Hom 复形是为一对两个图 (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顶点完全图K_n和当n为3或更大时的n循环图C_n。什么样的图是同伦测试图一直是该领域的中心话题。科兹洛夫在2006年猜想任何二分图都是同伦测试图，我解决了这个猜想。我们还发现了一个例子，其中相邻的配合物具有不同的色数，即使它们是同构的。这对 Lovasz 在其关于邻域复形的论文中所写的问题“图的色数的邻域复形是否存在拓扑特征？”给出了否定的答案。