Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
type: Item
instance of: scholarly article
title: Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
zbMATH Open document ID: 0902.05028
author: Béla Bollobás
published in: Documenta Mathematica
publication date: 1998-08-05T00:00:00Z
full work available at URL: https://eudml.org/doc/224709
full work available at URL: Bollobas.MAN.html
review text: 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}\)).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 51M16
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 1184372
zbMATH Keywords: graph properties
zbMATH Keywords: hereditary properties
zbMATH Keywords: monotone properties
zbMATH Keywords: forbidden subgraphs
reviewed by: Peter Brass
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1184372