Local and global colorability of graphs

It is shown that for any fixed c≥3c≥3 and rr, the maximum possible chromatic number of a graph on nn vertices in which every subgraph of radius at most rr is cc-colorable is Θ̃(n1r+1): it is O((n/logn)1r+1) and Ω(n1r+1/logn). The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random nn-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius rr in it are 2-degenerate.