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).