It is shown that for any fixed c3 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 Θ(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 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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Local chromatic number
- Local colorability