Deciding the Bell Number for Hereditary Graph Properties

Atminas, A, Collins, A, Foniok, J and Lozin, VV (2016) Deciding the Bell Number for Hereditary Graph Properties. SIAM Journal on Discrete Mathematics, 30. ISSN 0895-4801

Preview

Available under License In Copyright. Download (455kB) | Preview

Abstract

The paper [J. Balogh, B. Bollobás, D. Weinreich, J. Combin. 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 $\mathcal{F}$ of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set $\mathcal{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. Read More: http://epubs.siam.org/doi/abs/10.1137/15M1024214