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)
Plum Print visual indicator of research metrics
  • Citations
    • Citation Indexes: 5
  • Captures
    • Readers: 6
see details

Abstract

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
Volume30
Issue number2
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

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

Cite this

Atminas, A., Collins, A., Foniok, J., & Lozin, V. V. (2016). Deciding the bell number for hereditary graph properties. SIAM Journal on Discrete Mathematics, 30(2), 1015-1031. https://doi.org/10.1137/15M1024214