Coloring powers of random graphs
Alan Frieze, Ross J. Kang, Aditya Raut, Michelle Sweering, Hilde Verbeek · 2026
Read Coloring powers of random graphs by Alan Frieze, Ross J. Kang, Aditya Raut, Michelle Sweering, Hilde Verbeek (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14006.txt.
Description
Frieze and colleagues bound the maximum degree and chromatic number of powers of sparse random graphs with high probability. In the sparse regime they pin the degree's growth and sandwich the chromatic number between degree-based bounds, with equality at the top end when the power is 2. For denser graphs they give a matching order of growth for the chromatic number in terms of average degree.
Catalog record
| CREATOR | Alan Frieze, Ross J. Kang, Aditya Raut, Michelle Sweering, Hilde Verbeek |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36791 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14006