Article contents
On the Chromatic Number of Random Cayley Graphs
Published online by Cambridge University Press: 09 September 2016
Abstract
Let G be an abelian group of cardinality n, where hcf(n, 6) = 1, and let A be a random subset of G. Form a graph ΓA on vertex set G by joining x to y if and only if x + y ∈ A. Then, with high probability as n → ∞, the chromatic number χ(ΓA) is at most $(1 + o(1))\tfrac{n}{2\log_2 n}$. This is asymptotically sharp when G = ℤ/nℤ, n prime.
MSC classification
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2016
References
- 4
- Cited by