On the chromatic number of random Cayley graphs
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 probablilty as N → infinity, the chromatic number χ(ΓA) is at most (1 + o(1)) N/2 log2 N. This is asymptotic...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
Cambridge University Press
2016
|