Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424332 | European Journal of Combinatorics | 2013 | 12 Pages |
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.99log2n, 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.99log3p, the chromatic number of the Cayley graph of Zp 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>logp, the chromatic number is typically at least Ω(k/logp) and for k=Î(p) it is Î(plogp).For some non-abelian groups (like SL2(Zq)), 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.