Printable PDF
Department of Mathematics,
University of California San Diego

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

Graph Theory Seminar

Graeme Kemkes

UCSD

The Chromatic Number of a Random $d$-regular Graph

Abstract:

\indent A random $d$-regular graph is simply a graph, drawn uniformly at random, from the probability space of all $d$-regular graphs on $n$ vertices. Researchers are interested in the properties of this graph that hold with probability approaching 1 as the number of vertices grows large. In this talk we discuss some of the main results in this area and the tools that are used for proving them. We also describe a new result about the chromatic number. This is joint work with Xavier P\'{e}rez and Nick Wormald.

November 4, 2008

3:00 PM

AP&M 7321

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