Examples of topologically highly chromatic graphs with locally small chromatic number

Abstract

Kierstead, Szemerédi, and Trotter showed that a graph with at most $\lfloor r/(2n){\rfloor }^n$ vertices such that each ball of radius $r$ in it is $c$-colorable should have chromatic number at most $n(c-1)+1$. We show that this estimate is sharp in $r$. Namely, for every $n$, $r$, and $c$ we construct a graph $G$ containing $O((2rc{)}^{n-1}c)$ vertices such that $\chi (G)\ge n(c-1)+1$, although each ball of radius $r$ in $G$ is $c$-colorable. The core idea is the construction of a graph whose neighborhood complex is homotopy equivalent to the join of neighborhood complexes of two given graphs.

arXiv comment2 figures

Cited by in corpus (2)

• Number of vertices in graphs with locally small chromatic number and large chromatic number
• Local And Global Colorability of Graphs