Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
复制标题
计算机科学中的图论概念 - 第 40 届国际研讨会，WG 2014，法国 Nouan-le-Fuzelier，2014 年 6 月 25-27 日。修订后的精选论文
DOI：
10.1007/978-3-319-12340-0_6
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Atminas A
中科院分区：
文献类型：
--
作者：
Atminas A
本文[J.Balogh，B.BollobáS，D.Weinreich，A Jumping to the Bell Number for遗传图性质，J.Combin.理论系列。B95(2005)29-48]证明了遗传图性质的速度到Bell数的跳跃，并给出了速度至少为的极小类族的部分刻画。在本文中，我们给出了这个家族的一个完整的刻画。由于这个家族是无限的，因此确定一个遗传财产的速度是高于还是低于贝尔数的问题的可判性是值得怀疑的。对于有限多个禁止导出子图所定义的性质，我们给出了肯定的回答。换句话说，我们证明了存在一个算法，它在给定一个有限的图集的情况下，决定这类图的速度是大于还是低于Bell数。
The paper [J. Balogh, B. Bollobás, D. Weinreich, A jump to the Bell number for hereditary graph properties,J. Combin. Theory Ser. B95 (2005) 29–48] identifies a jump in the speed of hereditary graph properties to the Bell numberand provides a partial characterisation of the family of minimal classes whose speed is at least. In the present paper, we give a complete characterisation of this family. Since this family is infinite, the decidability of the problem of determining if the speed of a hereditary property is above or below the Bell number is questionable. We answer this question positively for properties defined by finitely many forbidden induced subgraphs. In other words, we show that there exists an algorithm which, given a finite setof graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the setis above or below the Bell number.