Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Paul Horn

Graduate Student, UCSD

The chromatic number of random graphs

Abstract:

The chromatic number $\chi(G)$ of a graph $G$ is one the most important graph invariants. It is known, due to Bollob\'as as well as Luczak, that for the random graph $G(n,p)$, $\chi(G(n,p)) \sim d/2\ln d$ where $d = np$ is the expected average degree. Similarly, Frieze and Luczak showed that for a random $d$-regular graph that $\chi(G_{n,d}) \sim d/2\ln d$. What can we say in the case where, instead of a $d$-regular graph, we instead look at a random graph with a given degree sequence ${\bf d} = (d_1,\dots,d_n)$ with average degree $d$? In this talk, I look at a recent preprint of Frieze, Krivelevich, and Smyth who show under a condition on ${\bf d}$ that $\chi(G_{n,{\bf d}}) = \Theta(d/\ln d)$. I also look some at the problem of translating this result to a random graph with a given expected degree sequence.

August 14, 2006

2:00 PM

AP&M 7321

****************************