The structure of hereditary properties and 2-coloured multigraphs (Q653987): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/s00493-011-2630-7 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S00493-011-2630-7 / rank | |||
Normal rank |
Revision as of 06:19, 9 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The structure of hereditary properties and 2-coloured multigraphs |
scientific article |
Statements
The structure of hereditary properties and 2-coloured multigraphs (English)
0 references
20 December 2011
0 references
A graph property \(P\) is a class of graphs closed under isomorphism; it is hereditary if it is closed under the taking of induced subgraphs. It is customary to say that graphs in the class \(P\) ``have the property \(P\)''. \textit{B. Bollobás} and \textit{A. Thomason} [Combinatorica 20, No. 2, 173--202 (2000; Zbl 0959.05105)] 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. A hereditary graph property \(P\) can be associated with a class of 2-coloured multigraphs. Given a graph \(G\), let \(cc(G)\) be the complete 2-coloured multigraph with vertex set \(V (G)\) in which the edges of \(G\) are coloured red and the edges of the complement of \(G\) are coloured blue. Then, given a property \(P\), let \(H(P)\) be the class of 2-coloured multigraphs defined by \(H(P)=\{cc(G): G \;\text{not in}\;P\}\). Note that every hereditary property \(P\) can be described by a family of forbidden (induced) subgraphs. In this note the authors show 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.
0 references
hereditary graph properties
0 references
extremal properties
0 references
2-coloured multigraphs
0 references