The Library
Deciding the Bell number for hereditary graph properties
Tools
Atminas, Aistis, Collins, Andrew, Foniok, J. and Lozin, Vadim V. (2016) Deciding the Bell number for hereditary graph properties. SIAM Journal on Discrete Mathematics, 30 (2). pp. 1015-1031. doi:10.1137/15M1024214 ISSN 0895-4801.
PDF
WRAP_Atminas_15m1024214.pdf - Published Version - Requires a PDF viewer. Download (724Kb) |
|
PDF
abovebellall3.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (250Kb) |
Official URL: http://dx.doi.org/10.1137/15M1024214
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
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||||
ISSN: | 0895-4801 | ||||||||||
Official Date: | 2016 | ||||||||||
Dates: |
|
||||||||||
Volume: | 30 | ||||||||||
Number: | 2 | ||||||||||
Page Range: | pp. 1015-1031 | ||||||||||
DOI: | 10.1137/15M1024214 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Date of first compliant deposit: | 3 May 2016 | ||||||||||
Date of first compliant Open Access: | 22 August 2016 | ||||||||||
Adapted As: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year