Local And Global Colorability of Graphs

Abstract

It is shown that for any fixed $c\ge 3$ and $r$, the maximum possible chromatic number of a graph on $n$ vertices in which every subgraph of radius at most $r$ is $c$ colorable is $\tilde{\Theta }\left(n^{\frac{1}{r+1}}\right)$ (that is, $n^{\frac{1}{r+1}}$ up to a factor poly-logarithmic in $n$). The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random $n$-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius $r$ in it are $2$-degenerate.

References in corpus (2)

• Examples of topologically highly chromatic graphs with locally small chromatic number
• Number of vertices in graphs with locally small chromatic number and large chromatic number