The structure of almost all graphs in a hereditary property
The structure of almost all graphs in a hereditary property
复制标题
遗传财产中几乎所有图形的结构
DOI：
10.1016/j.jctb.2010.10.001
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Morris
中科院分区：
文献类型：
--
作者：
N. Alon;J. Balogh;B. Bollobás;R. Morris
图的一个遗传性质是在导出子图下闭的图的集合。P的速度是n的函数，|PN| Alekseev、Bollobás和P.S. ason证明了：如果P是图的遗传性质，则其中r=r（P）∈N是P的所谓“着色数”，然而，他们的结果对典型图G∈P的结构知之甚少.在本文中，我们描述的结构几乎每一个图的遗传性质的图，P.作为一个结果，我们得出基本上最佳的界限的速度P，改善Alekseev-Bollobás-Bollobason定理，也推广结果Balogh，Bollobás和Simonovits。
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 Pndenotes 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 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–Bollobás–Thomason Theorem, and also generalising results of Balogh, Bollobás and Simonovits.