Name
Abstract | ||
|---|---|---|
In “The structure of hereditary properties and colourings of random graphs” [Combinatorica 20(2) (2000), 173–202], Bollobás and the second author studied the probability of a hereditary property P in the probability space G(n,p). They found simple properties that closely approximate P in this space, and using these simple properties they determined the P-chromatic number of random graphs. In this note we point out that the analysis of hereditary properties in G(n,p) can be made more exact by means of the extremal properties of 2-coloured multigraphs, and we illustrate some cases in which the probability of P can thereby be calculated. At the same time we correct a mistake in the cited paper. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00493-011-2630-7 | Combinatorica |
Keywords | Field | DocType |
random graph,p-chromatic number,hereditary property p,probability space g,approximate p,hereditary property,2-coloured multigraphs,extremal property,simple property | Discrete mathematics,Combinatorics,Random graph,Mistake,Probability space,Hereditary property,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 0209-9683 |
Citations | PageRank | References |
4 | 0.58 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edward Marchant | 1 | 4 | 0.58 |
| Andrew Thomason | 2 | 71 | 16.01 |