The structure of hereditary properties and 2-coloured multigraphs (Q653987)

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.