The chromatic number of random graphs
type: Item
instance of: scholarly article
title: The chromatic number of random graphs
zbMATH Open document ID: 0666.05033
DOI: 10.1007/BF02122551
author: Béla Bollobás
published in: Combinatorica
publication date: 1988-01-01T00:00:00Z
review text: Let \(G_ p\) denote a random graph with vertex set \(\{\) 1,2,...,n\(\}\), in which the edges are chosen independently and with probability \(p=p(n)\), \(0<p<1\). The main aim of the paper is the study of the clique number \(cl(G_ p)\) and chromatic number \(\chi (G_ p)\) of \(G_ p\) for p constant. The notation and terminology used are standard. It is proved that for a fixed probability p, \(0<p<1\), almost every random graph \(G_{n,p}\) has chromatic number \[ (+o(1))\log (1/(1-p))\frac{n}{\log n}. \] This result improves the estimation of \(\chi (G_ p)\) presented in \textit{D. W. Matula} [ibid. 7, 275-284 (1987; Zbl 0648.05049)] and is best possible. Further, some results concerning independent sets and the chromatic number of graphs \(G_ p\) for varying probabilities are sketched.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 4089577
zbMATH Keywords: random graph
zbMATH Keywords: clique number
zbMATH Keywords: chromatic number
zbMATH Keywords: independent sets
reviewed by: Ulrike Baumann
Wikidata QID: Q93437532
MaRDI profile type: Publication
cites work: Weighted sums of certain dependent random variables
cites work: Q3344024
cites work: Cliques in random graphs
cites work: Q3715148
cites work: Q4065548
cites work: On tail probabilities for martingales
cites work: On colouring random graphs
cites work: Q3884128
cites work: On the chromatic forcing number of a random graph
cites work: Expose-and-merge exploration and the chromatic number of a random graph
cites work: Q4183227
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: On the Dimension of the l n p -Subspaces of Banach Spaces, for 1 p < 2
cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
cites work: Random embeddings of Euclidean spaces in sequence spaces
cites work: Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
full work available at URL: https://doi.org/10.1007/bf02122551
OpenAlex ID: W2082249316
description: scientific article; zbMATH DE number 4089577