Box complex and the chromatic number of a graph

開催日時
2014/07/23 水 15:30 - 17:00
場所
3号館108号室
講演者
松下尚弘
講演者所属
東京大学
概要

To compute the chromatic number of a graph is called the graph coloring problem which has been investigated for a long time in graph theory. Box complex is a $\mathbb{Z}_2$-space associated to a graph, whose homotopy invariant is known to be related to the chromatic number.
In this talk, we introduce some crucial examples of graphs about box complexes. First we show that there are graphs whose box complexes are $\mathbb{Z}_2$-homotopy equivalent but whose chromatic numbers are different. We will also talk about the graphs whose box complexes are homeomorphic but whose chromatic numbers are different.