# Princeton Discrete Math Seminar

## Title:

Randomized Greedy Colourings

## Place:

- Fine Hall, Room 224
- Princeton University.

## Time:

- 2:30 p.m.
- Wednesday, November 27, 1996

Abstract:
A general "randomized greedy colouring" (RGC) is a stochastic
process S(t), with t in [0,T], of partial proper colourings of a
graph G = (V,E), such that, for s > t, S(s) is an extension of S(t).
We assume that the final colouring S(T) has domain V.

I discuss a fairly general construction of an RGC that can be used to
obtain results in extremal combinatorics. It is closely related to
variants of the "nibble method".

As a primary application, I consider asymptotic Brook's type bounds
for various classes of "sparse" graphs. For instance, the chromatic
number (or the choice number) of a triangle free graph is at most
(8 + o(1)) D / log D,
where D is the maximum degree. For K(r)-free graphs one obtains similar
but less nice bounds.

Furthermore, since the entropy of the distribution of the final
colouring S(T) by construction is bounded from below, one can obtain
quite good lower bounds for the number of colourings.

The construction extends to edge and vertex colourings of hypergraphs
as well as to the problem of finding independent sets in graphs or
hypergraphs, and possibly to other problems.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu).

Document last modified on November 21, 1996