DECIDING THE BELL NUMBER FOR HEREDITARY GRAPH PROPERTIES

作者：Atminas Aistis^*; Collins Andrew; Foniok Jan; Lozin Vadim V

来源：SIAM Journal on Discrete Mathematics, 2016, 30(2): 1015-1031.

DOI：10.1137/15M1024214

• hereditary class of graphs
• speed of hereditary properties
• Bell number
• decidability

The paper [J. Balogh, B. Bollobas, D. Weinreich, T. Cominn. Theory Ser. B, 95 (2005), pp. 29-48] identifies a jump in the speed of hereditary graph properties to the Bell number B-n and provides a partial characterization of the family of minimal classes whose speed is at least B-n. In the present paper, we give a complete characterization 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 by showing that there exists an algorithm which, given a finite set F of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set F is above or below the Bell number. For properties defined by infinitely many minimal forbidden induced subgraphs, the speed is known to be above the Bell number.

• 出版日期2016