# Local and global colorability of graphs

Sun, 03/04/2016 - 14:00

Speaker:

Omri Ben Eliezer ׂ(Tel-Aviv University)

Seminar:

Place:

Math building, 3rd floor seminar room (216/201)

Abstract:

It is shown that for any fixed c \geq 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 n^(1/r+1) up to a multiplicative factor logarithmic in n: in fact, it is O((n/log(n)) ^ (1/r+1)) and Omega(n^(1/r+1) / log(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.

- Last modified: 29/03/2016