The structure of hereditary properties and 2-coloured multigraphs (Q653987): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
(2 intermediate revisions by one other user not shown)
Property / DOI
 
Property / DOI: 10.1007/s00493-011-2630-7 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00493-011-2630-7 / rank
 
Normal rank

Latest revision as of 23:56, 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
    0 references
    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
    0 references
    hereditary graph properties
    0 references
    extremal properties
    0 references
    2-coloured multigraphs
    0 references

    Identifiers