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

CREATORAlan Frieze, Ross J. Kang, Aditya Raut, Michelle Sweering, Hilde Verbeek
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36791
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.14006

Browse the full library · About the Tower of Babel