Asymptotic Normality of the Chromatic Number of a Random Graph

2015/01/22 by Ali Rejali, Rejali, Ali, Farkhondeh Alsadat Sajadi +1
Mathematics · #05C15 #60F05 #60G42 #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Primary 05C80 #Probability (math.PR) #Secondary 05D40 #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1501.05471

openalex publication_date 2015/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we prove that the limiting distribution of the Chromatic number of a random graph G_n,p, with fixed edge-probability p, after appropriate centering and scaling is Normal, when the number of vertices n, goes to infinity.

Citations

• Increasing the chromatic number of a random graph

Related

• The oriented chromatic number of random graphs of bounded degree
• The clique chromatic number of sparse random graphs
• The set chromatic number of random graphs
• Clique colouring of binomial random graphs
• The chromatic number of very dense random graphs