### Abstract

A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of P is the function n→|Pn|, where Pn denotes the graphs of order n in P. It was shown by Alekseev, and by Bollobás and Thomason, that if P is a hereditary property of graphs then. |Pn|=2(1-1/r+o(1))(n2), where r=r(P)j{cyrillic,ukrainian}N is the so-called 'colouring number' of P. However, their results tell us very little about the structure of a typical graph GεP. In this paper we describe the structure of almost every graph in a hereditary property of graphs, P. As a consequence, we derive essentially optimal bounds on the speed of P, improving the Alekseev-Bollobás-Thomason Theorem, and also generalising results of Balogh, Bollobás and Simonovits.

Original language | English (US) |
---|---|

Pages (from-to) | 85-110 |

Number of pages | 26 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 101 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1 2011 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Entropy
- Hereditary property
- Structure of graphs

## Fingerprint Dive into the research topics of 'The structure of almost all graphs in a hereditary property'. Together they form a unique fingerprint.

## Cite this

*Journal of Combinatorial Theory. Series B*,

*101*(2), 85-110. https://doi.org/10.1016/j.jctb.2010.10.001