The structure of hereditary properties and colourings of random graphs (Q5928567): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004930070019 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2018242275 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 21:53, 19 March 2024
scientific article; zbMATH DE number 1583102
Language | Label | Description | Also known as |
---|---|---|---|
English | The structure of hereditary properties and colourings of random graphs |
scientific article; zbMATH DE number 1583102 |
Statements
The structure of hereditary properties and colourings of random graphs (English)
0 references
1 April 2001
0 references
If \({\mathcal P}\) is a non-trivial hereditary graph property, \(0<p<1\), then the \({\mathcal P}\)-chromatic number of \(G_{n,p}\) is a.s. asymptotically \(c_pn/2\log_2 n\) where \(c_p=c_p({\mathcal P})=\lim_{k} c_{k,p}\) and \(P[G_{k,p}\in {\mathcal P}]= 2^{-c_{k,p}{{k}\choose{2}}}\). For this, it is shown that \(c_p({\mathcal P})\) can be approximated to \(c_p({\mathcal P}')\) where \({\mathcal P}'\subseteq {\mathcal P}\) is a class of very simple graphs.
0 references
random graphs
0 references
colouring
0 references