Local and global colorability of graphs

Seminar
Speaker
Omri Ben Eliezer ׂ(Tel-Aviv University)
Date
03/04/2016 - 15:30 - 14:00Add to Calendar 2016-04-03 14:00:00 2016-04-03 15:30:00 Local and global colorability of graphs 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. Math building, 3rd floor seminar room (216/201) אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
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.

תאריך עדכון אחרון : 29/03/2016