Non-existence of homotopical upper bounds for the chromatic number
Takahiro Matsushita · arXiv (Cornell University) · 2015
Hom complex ${\rm Hom} (T,G)$ is a CW-complex which is a generalization of neighborhood complex introduced by Lov\'asz in his proof of Kneser's conjecture. If $T$ belongs to a certain class of graphs, including complete graphs $K_n$ and odd cycles $C_{2r+1}$, then it is known that the connectivity of the Hom complex ${\rm Hom}(T,G)$ gives a lower bound for the chromatic number of $G$. On the other hand, we show that for a finite family $\mathcal{F}$ of finite graphs, for a non-bipartite graph $G$, and for an integer $m$, there is an inclusion $G \hookrightarrow H$ which induces a homotopy equivalence ${\rm Hom}(T,G) \rightarrow {\rm Hom}(T,H)$ for all $T \in \mathcal{F}$, but $\chi(H) \geq \chi(G) + n$.