Asymptotic Normality of the Chromatic Number of a Random Graph

MaRDI QIDQ6258353zbMATH OpenFDO

Authors Ali Rejali, Farkhondeh A. Sajadi

Publication date 22 January 2015

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Central limit and other weak theorems (60F05) Martingales with discrete parameter (60G42)

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

This page was built for publication: Asymptotic Normality of the Chromatic Number of a Random Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6258353)