Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring (Q1126826): Difference between revisions

A hereditary graph property \(\mathcal P\) is a class of graphs that contains infinitely many graphs and is closed under taking induced subgraphs. This paper gives a survey of results on hereditary properties \({\mathcal P}\), especially on the growth rate of the number of graphs of order \(n\) in \({\mathcal P}\) (size of \({\mathcal P}\)), on the structure of \({\mathcal P}\) in terms of forbidden subgraphs, and on the behaviour of the \({\mathcal P}\)-chromatic number (where each color class is required to be a graph of \({\mathcal P}\)).