A note on the chromatic number of the square of a sparse random graph

2023/12/06 by Alan Frieze, Frieze, Alan, Aditya Raut +1
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Topological and Geometric Data Analysis #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2312.03563

Abstract

We show that w.h.p the list chromatic number χ_ℓ of the square of G_n,p for p=c/n is asymptotically equal to the maximum degree Δ(G_n,p). Since χ(G²_n,p)≤ χ_ℓ(G²_n,p), this also improves an earlier result of Garapaty et al \citeKLMP who proved that χ(G²_n,p) ≤ 6 ⋅ Δ(G_n,p) w.h.p.

Related

• The clique chromatic number of sparse random graphs
• The oriented chromatic number of random graphs of bounded degree
• Chromatic thresholds in sparse random graphs
• Lower bounds on the chromatic number of random graphs
• On the game chromatic number of sparse random graphs