PreprintarXiv licencearXiv
Coloring sparse random Cayley graphs
Abstract
It is shown that there exists c > 0 so that the Cayley graph over any finite abelian group Z generated by c log |Z| random elements is properly 3-colorable with high probability (as |Z| → ∞). This is asymptotically tight and improves the best-known bound due to Alon of 1/4log log |Z| elements. It also settles the abelian case of Alon's suggestion that a bound of c log |G| may hold for any finite solvable group G.
Related
- COLORING SEMIMINIMAL CAYLEY GRAPHS
- Coloring Monomial Cayley Graphs: The One-Parameter Case
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- On (1,24) and (1,25)-packing edge-coloring of sparse subcubic graphs
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
BibTeX
@misc{tung2026coloring,
title = {{Coloring sparse random Cayley graphs}},
author = {Nathan Tung},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2606.23762},
eprint = {2606.23762},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.23762},
}
RIS
TY - UNPB
TI - Coloring sparse random Cayley graphs
AU - Nathan Tung
PY - 2026
DA - 2026/08/12
PB - arXiv
DO - 10.48550/arxiv.2606.23762
UR - https://arxiv.org/abs/2606.23762
AB - It is shown that there exists c > 0 so that the Cayley graph over any finite abelian group Z generated by c log |Z| random elements is properly 3-colorable with high probability (as |Z| → ∞). This is asymptotically tight and improves the best-known bound due to Alon of 1/4log log |Z| elements. It also settles the abelian case of Alon's suggestion that a bound of c log |G| may hold for any finite solvable group G.
ER -