Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T09:35:31.133Z Has data issue: false hasContentIssue false
  • English
  • Français

Subcritical Graph Classes Containing All Planar Graphs

Part of: Combinatorics Graph theory

Published online by Cambridge University Press:  22 March 2018

AGELOS GEORGAKOPOULOS  and
STEPHAN WAGNER
AGELOS GEORGAKOPOULOS
Affiliation:
Mathematics Institute, University of Warwick, CV4 7AL, UK
STEPHAN WAGNER
Affiliation:
Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa (e-mail: swagner@sun.ac.za)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We construct minor-closed addable families of graphs that are subcritical and contain all planar graphs. This contradicts (one direction of) a well-known conjecture of Noy.

MSC classification

Primary: 05C30: Enumeration in graph theory
Secondary: 05A16: Asymptotic enumeration 05C10: Planar graphs; geometric and topological aspects of graph theory 05C80: Random graphs 05C83: Graph minors

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 763 - 773
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

Supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 639046).

‡

Supported by the National Research Foundation of South Africa, grant number 96236.

References

[1] Bernasconi, N., Panagiotou, K. and Steger, A. (2009) The degree sequence of random graphs from subcritical classes. Combin. Probab. Comput. 18 647–681.Google Scholar
[2] Corless, R. M., Gonnet, G. H., Hare, D. E. G., Jeffrey, D. J. and Knuth, D. E. (1996) On the Lambert W function. Adv. Comput. Math. 5 329–359.Google Scholar
[3] Drmota, M. (2009) Random Trees, Springer.Google Scholar
[4] Drmota, M., Fusy, E., Kang, M., Kraus, V. and Rué, J. (2011) Asymptotic study of subcritical graph classes. SIAM J. Discrete Math. 25 1615–1651.Google Scholar
[5] Drmota, M. and Noy, M. (2013), Extremal parameters in sub-critical graph classes. In Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM, pp. 1–7.Google Scholar
[6] Drmota, M., Ramos, L. and Rué, J. (2017) Subgraph statistics in subcritical graph classes. Random Struct. Alg. 51 631–673.Google Scholar
[7] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[8] Georgakopoulos, A. and Wagner, S. (2015) Limits of subcritical random graphs and random graphs with excluded minors. arXiv:1512.03572Google Scholar
[9] Giménez, O. and Noy, M. (2009) Asymptotic enumeration and limit laws of planar graphs. J. Amer. Math. Soc. 22 309–329.Google Scholar
[10] Goldschmidt, C. (2016) A short introduction to random trees. Mongolian Math. J. 20 53–72.Google Scholar
[11] Harary, F. and Palmer, E. M. (1973) Graphical Enumeration, Academic Press.Google Scholar
[12] Josuat-Vergès, M. (2015) Derivatives of the tree function. Ramanujan J. 38 1–15.Google Scholar
[13] Kurauskas, V. and McDiarmid, C. (2011) Random graphs with few disjoint cycles. Combin. Probab. Comput. 20 763–775.Google Scholar
[14] Norine, S., Seymour, P., Thomas, R. and Wollan, P. (2006) Proper minor-closed families are small. J. Combin. Theory Ser. B 96 754–757.Google Scholar
[15] Noy, M. (2014) Random planar graphs and beyond. In Proceedings of the International Congress of Mathematicians, Seoul 2014, Vol. IV, pp. 407–430.Google Scholar
[16] Panagiotou, K., Stufler, B. and Weller, K. (2016) Scaling limits of random graphs from subcritical classes. Ann. Probab. 44 3291–3334.Google Scholar
[17] Robertson, N. and Seymour, P. (1986) Graph minors V: Excluding a planar graph. J. Combin. Theory Ser. B 41 92–114.Google Scholar
[18] Stufler, B. (2015) Random enriched trees with applications to random graphs. arXiv:1504.02006Google Scholar