# Box complex and the chromatic number of a graph

Date:

2014/07/23 Wed 15:30 - 17:00

Room:

Room 108, Building No.3

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.