Number of vertices in graphs with locally small chromatic number and large chromatic number

Abstract

We discuss the minimal number of vertices in a graph with a large chromatic number such that each ball of a fixed radius in it has a small chromatic number. It is shown that for every graph $G$ on $\sim ((n+rc)/(c+rc){)}^{r+1}$ vertices such that each ball of radius $r$ is properly $c$-colorable, we have $\chi (G)\le n$.

References in corpus (1)

• Examples of topologically highly chromatic graphs with locally small chromatic number

Cited by in corpus (1)

• Local And Global Colorability of Graphs