The structure of hereditary properties and 2-coloured multigraphs
type: Item
instance of: scholarly article
title: The structure of hereditary properties and 2-coloured multigraphs
zbMATH Open document ID: 1249.05200
author: Edward Marchant
author: Andrew Thomason
published in: Combinatorica
publication date: 2011-12-20T00:00:00Z
review text: 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.
reviewed by: Michael Hager
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5990944
zbMATH Keywords: hereditary graph properties
zbMATH Keywords: extremal properties
zbMATH Keywords: 2-coloured multigraphs
MaRDI profile type: Publication
full work available at URL: s00493-011-2630-7
OpenAlex ID: W1993010909
cites work: On the entropy values of hereditary classes of graphs
cites work: What is the furthest graph from a hereditary property?
cites work: On the editing distance of graphs
cites work: Edit distance and its computation
cites work: Projections of Bodies and Hereditary Properties of Hypergraphs
cites work: Q5688999
cites work: The structure of hereditary properties and colourings of random graphs
cites work: Extremal problems for directed graphs
cites work: Algorithmic Solution of Extremal Digraph Problems
cites work: Q3060864
cites work: Q4273843
DOI: 10.1007/S00493-011-2630-7
Recommended article: Largest subgraph from a hereditary property in a random graph
Recommended article: The structure of almost all graphs in a hereditary property
Recommended article: On generalized graph colorings
Recommended article: Generalized Chromatic Numbers of Random Graphs
Recommended article: Q3797229
Recommended article: Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
Recommended article: The structure of hereditary properties and colourings of random graphs
Recommended article: Generalized chromatic numbers of random graphs
description: scientific article; zbMATH DE number 5990944