## 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 language | English |
---|---|

Pages (from-to) | 1015-1031 |

Number of pages | 17 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 30 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2016 |

Externally published | Yes |

## Keywords

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