Local and global colorability of graphs
Local and global colorability of graphs

Omri Ben Eliezer , Tel Aviv University and IAS
Fine Hall 224
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 ccolorable is equal to n^{1/(r+1)} up to a factor polylogarithmic 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 nvertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2degenerate. Joint work with Noga Alon.