The chromatic number of random Cayley graphs

DOI10.1016/j.ejc.2013.05.007zbMath1295.05206OpenAlexW1967114635MaRDI QIDQ2509709

Noga Alon

Publication date: 29 July 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2013.05.007

zbMATH Keywords

Diophantine approximationinteger distance graphslonely runner problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Correlation among runners and some results on the lonely runner conjecture ⋮ On the chromatic number of structured Cayley graphs ⋮ One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{F}_2^n$ ⋮ Chromatic numbers of Cayley graphs of abelian groups: a matrix method ⋮ Random runners are very lonely ⋮ On the Chromatic Number of Random Cayley Graphs ⋮ The lonely runner problem for lacunary sequences ⋮ LONELY RUNNERS IN FUNCTION FIELDS ⋮ Some remarks on the lonely runner conjecture ⋮ Distinguishing chromatic number of random Cayley graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Random runners are very lonely
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Large sets in finite fields are sumsets
• Ramanujan graphs
• Uniform dilations
• On the chromatic number of cube-like graphs
• Coloring graphs with sparse neighborhoods
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• List coloring of random and pseudo-random graphs
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• Random Latin square graphs
• Random Cayley graphs and expanders
• Repeated communication and Ramsey graphs
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• Minimum partition of a matroid into independent subsets
• ON EIGENVALUES AND COLORINGS OF GRAPHS, II
• Circular chromatic number: A survey

This page was built for publication: The chromatic number of random Cayley graphs