On the chromatic number of random Cayley graphs

Let G be an abelian group of cardinality N, where (N,6) = 1, and let A be a
random subset of G. Form a graph Gamma_A on vertex set G by joining x to y if
and only if x + y is in A. Then, almost surely as N tends to infinity, the
chromatic number chi(Gamma_A) is at most (1 + o(1))N/2 log_2 N. This is
asymptotically sharp when G = Z/NZ, N prime.
Presented at the conference in honour of Bela Bollobas on his 70th birthday,
Cambridge August 2013.