## Abstract

We consider the typical behavior of the chromatic number of a random Cayley graph of a given group of order n with respect to a randomly chosen set of size k ≤ n / 2. This behavior depends on the group: for some groups it is typically 2 for all k < 0.99_{log 2}n, whereas for some other groups it grows whenever k grows. The results obtained include a proof that for any large prime p, and any 1 ≤ k ≤ 0.99_{log 3}p, the chromatic number of the Cayley graph of _{Z p} with respect to a uniform random set of k generators is, asymptotically almost surely, precisely 3. This strengthens a recent result of Czerwiński. On the other hand, for k > log p, the chromatic number is typically at least Ω(k/logp) and for k = Θ (p) it is Θ(plogp).For some non-abelian groups (like S_{L2} (_{Z q}) ), the chromatic number is, asymptotically almost surely, at least ^{kΩ (1) } for every k, whereas for elementary abelian 2-groups of order n = ^{2t} and any k satisfying 1.001t ≤ k ≤ 2.999t the chromatic number is, asymptotically almost surely, precisely 4. Despite these discrepancies between different groups, it seems plausible to conjecture that for any group of order n and any k ≤ n / 2, the typical chromatic number of the corresponding Cayley graph cannot differ from k by more than a poly-logarithmic factor in n.

Original language | English (US) |
---|---|

Pages (from-to) | 1232-1243 |

Number of pages | 12 |

Journal | European Journal of Combinatorics |

Volume | 34 |

Issue number | 8 |

DOIs | |

State | Published - Nov 2013 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics