##### 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

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