Deciding the bell number for hereditary graph properties

Aistis Atminas, Andrew Collins, Jan Foniok, Vadim V. Lozin

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Identifies a jump in the speed of hereditary graph properties to the Bell number Bn and provides a partial characterization of the family of minimal classes whose speed is at least Bn. 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.

Original languageEnglish
Pages (from-to)1015-1031
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - 2016
Externally publishedYes


  • Bell number
  • Decidability
  • Hereditary class of graphs
  • Speed of hereditary properties

Cite this