Deciding the Bell number for hereditary graph properties

DOI10.1007/978-3-319-12340-0_6MaRDI QIDQ5892155zbMATH OpenOpenAlexFDO

Authors Aistis Atminas, Jan Foniok, Andrew Collins, Vadim Lozin

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.3118, https://e-space.mmu.ac.uk/617924/1/1405.3118v3.pdf

zbMATH Keywords

Bell numberdecidabilityhereditary class of graphsspeed of hereditary properties

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Bell and Stirling numbers (11B73)

Abstract: The paper [J. Balogh, B. Bollob'{a}s, D. Weinreich, A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005) 29--48] identifies a jump in the speed of hereditary graph properties to the Bell number $B_n$ and provides a partial characterisation of the family of minimal classes whose speed is at least $B_n$. In the present paper, we give a complete characterisation 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 $mathcalF$ of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set $mathcalF$ 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.

Recommendations

• Deciding the Bell number for hereditary graph properties
• A jump to the Bell number for hereditary graph properties
• Well‐quasi‐ordering and finite distinguishing number
• The unlabelled speed of a hereditary graph property
• A note on the speed of hereditary graph properties

Cited in

(3)

• A jump to the Bell number for hereditary graph properties
• scientific article; zbMATH DE number 7471007 (Why is no real title available?)
• Deciding the Bell number for hereditary graph properties

This page was built for publication: Deciding the Bell number for hereditary graph properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892155)