Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract) Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Deciding the Bell Number for Hereditary Graph Properties

(Extended Abstract)

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

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The paper [J. Balogh, B. Bollobá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 for properties defined by finitely many forbidden induced subgraphs. In other words, we show 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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Vertex Contact Graphs of Paths on a Grid
next chapter Boxicity and Separation Dimension
Footnotes
1
Throughout the paper we use the two terms – graph property and class of graphs – interchangeably.
 
Literature
1.
Alekseev, V.E.: Range of values of entropy of hereditary classes of graphs. Diskret. Mat. 4(2), 148–157 (1992). (in Russian); translation in Discrete Math. Appl. 3(2), 191–199 (1993)
2.
Alekseev, V.E.: On lower layers of a lattice of hereditary classes of graphs. Diskretn. Anal. Issled. Oper. Ser. 1 4(1), 3–12 (1997). (in Russian)MathSciNetMATH
3.
Allen, P., Lozin, V., Rao, M.: Clique-width and the speed of hereditary properties. Electron. J. Combin. 16(1), Research Paper 35, 11 p. (2009)
4.
Alon, N., Balogh, J., Bollobás, B., Morris, R.: The structure of almost all graphs in a hereditary property. J. Combin. Theory Ser. B 101(2), 85–110 (2011)MathSciNetCrossRefMATH
5.
Balogh, J., Bollobás, B., Weinreich, D.: The speed of hereditary properties of graphs. J. Combin. Theory Ser. B 79(2), 131–156 (2000)MathSciNetCrossRefMATH
6.
Balogh, J., Bollobás, B., Weinreich, D.: The penultimate rate of growth for graph properties. Eur. J. Combin. 22(3), 277–289 (2001)CrossRefMATH
7.
Balogh, J., Bollobás, B., Weinreich, D.: A jump to the Bell number for hereditary graph properties. J. Combin. Theory Ser. B 95(1), 29–48 (2005)MathSciNetCrossRefMATH
8.
Chvátal, V., Hammer, P.L.: Set-packing and threshold graphs. Res. Report CORR 73–21, Comp. Sci. Dept. Univ. of Waterloo (1973)
9.
Erdős, P., Frankl, P., Rödl, V.: The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2(2), 113–121 (1986)MathSciNetCrossRef
10.
Erdős, P., Kleitman, D.J., Rothschild, B.L.: Asymptotic enumeration of \(K_n\)-free graphs. Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, number 17 in Atti dei Convegni Lincei, pp. 19–27. Accad. Naz. Lincei, Rome (1976)
11.
Kolaitis, P.G., Prömel, H.J., Rothschild, B.L.: \(K_{l+1}\)-free graphs: asymptotic structure and a 0–1 law. Trans. Amer. Math. Soc. 303(2), 637–671 (1987)MathSciNetMATH
12.
13.
Prömel, H.J., Steger, A.: Excluding induced subgraphs: quadrilaterals. Random Struct. Algorithms 2(1), 55–71 (1991)CrossRefMATH
14.
Prömel, H.J., Steger, A.: Excluding induced subgraphs. III. A general asymptotic. Random Struct. Algorithms 3(1), 19–31 (1992)CrossRefMATH
15.
16.
17.
Metadata
Title
Deciding the Bell Number for Hereditary Graph Properties
Authors
Aistis Atminas
Andrew Collins
Jan Foniok
Vadim V. Lozin
Copyright Year
2014
Book
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-12339-4

Electronic ISBN: 978-3-319-12340-0

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-12340-0_6

Premium Partner

    Image Credits