Name
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@?|P"n|, where P"n denotes the graphs of order n in P. It was shown by Alekseev, and by Bollobas and Thomason, that if P is a hereditary property of graphs then|P"n|=2^(^1^-^1^/^r^+^o^(^1^)^)^(^n^2^), where r=r(P)@?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-Bollobas-Thomason Theorem, and also generalising results of Balogh, Bollobas and Simonovits. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jctb.2010.10.001 | Journal of Chemical Thermodynamics |
Keywords | Field | DocType |
hereditary property,order n,function n,generalising result,optimal bound,colouring number,induced subgraphs,typical graph,n denotes,alekseev-bollobas-thomason theorem,entropy,structure of graphs | Graph,Discrete mathematics,Combinatorics,Indifference graph,Hereditary property,Chordal graph,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
101 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
23 | 1.29 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| József Balogh | 2 | 862 | 89.91 |
| Béla Bollobás | 3 | 2696 | 474.16 |
| Robert Morris | 4 | 101 | 13.12 |