Box complex and the chromatic number of a graph

Date
2014/07/23 Wed 15:30 - 17:00
Room
3号館108号室
Speaker
Takahiro Matsushita
Affiliation
The University of Tokyo
Abstract

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.