printable pdf
比利时vs摩洛哥足彩 ,
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

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