Local and global colorability of graphs

-
Omri Ben Eliezer , Tel Aviv University and IAS

It is shown that for any fixed c > 2 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 equal to n^{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. Joint work with Noga Alon.