Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-14T07:26:02.718Z Has data issue: false hasContentIssue false
  • English
  • Français

Subcritical Graph Classes Containing All Planar Graphs

Part of: Graph theory Combinatorics

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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 763 - 773
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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