On random graphs from a minor-closed class

doi:10.1017/CBO9781316479988.005

4 - On random graphs from a minor-closed class

Published online by Cambridge University Press: 05 May 2016

Michael Krivelevich ,

Konstantinos Panagiotou ,

Mathew Penrose and

Colin McDiarmid

Edited by

Nikolaos Fountoulakis and

Dan Hefetz

Show author details

Michael Krivelevich: Affiliation:
Tel-Aviv University
Konstantinos Panagiotou: Affiliation:
Universität Munchen
Mathew Penrose: Affiliation:
University of Bath
Colin McDiarmid: Affiliation:
University of Oxford
Nikolaos Fountoulakis: Affiliation:
University of Birmingham
Dan Hefetz: Affiliation:
University of Birmingham

Book contents

Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'

Type: Chapter
Information: Random Graphs, Geometry and Asymptotic Structure , pp. 102 - 120

DOI: https://doi.org/10.1017/CBO9781316479988.005 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2016

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.)

Book purchase

Temporarily unavailable

References

[1] A., Denise, M., Vasconcellos, and D., Welsh, The random planar graph, Congr. Numer. 113 (1996), 61–79.Google Scholar

[2] P., Flajolet and R., Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.Google Scholar

[3] O., Giménez and M., Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc., 22 (2009), 309–329.Google Scholar

[4] E.A., Bender, Z., Gao, and N.C., Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin., 9 (2002), #R43.Google Scholar

[5] G., Chapuy, E., Fusy, O., Giménez, B., Mohar, and M., Noy, Asymptotic enumeration and limit laws for graphs of fixed genus, J. Combin. Theory A, 118 (2011), 748–777.Google Scholar

[6] E., Bender and Z., Gao, Asymptotic enumeration of labelled graphs with a given genus, Electron. J. Combin., 18 (2011), #P13.Google Scholar

[7] N., Robertson and P.D., Seymour, Graph minors I–XX, J. Combin. Theory B (1983–2004).Google Scholar

[8] R., Diestel, Graph Theory, 4th edn., Springer-Verlag, Heidelberg, 2010.Google Scholar

[9] W., Mader, Homomorphiesätze für Graphen, Math. Ann., 178 (1968), 154–168.Google Scholar

[10] A.V., Kostochka, The minimum Hadwiger number for graphs of a given mean degree of vertices (in Russian), Metody Diskret. Anal., 38 (1982), 37–58.Google Scholar

[11] A., Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc., 95 (1984), 261–265.Google Scholar

[12] S., Norine, P., Seymour, R., Thomas, and P., Wollan, Proper minor-closed families are small, J. Combin. Theory B, 96 (2006), 754–757.Google Scholar

[13] Z., Dvorák and S., Norine, Small graph classes and bounded expansion, J. Combin. Theory B, 100 (2010), 171–175.Google Scholar

[14] C., McDiarmid, A., Steger, and D., Welsh, Random planar graphs, J. Combin. Theory B, 93 (2005), 187–206.Google Scholar

[15] A., Rényi, Some remarks on the theory of trees, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 4 (1959), 73–85.Google Scholar

[16] M., Drmota, Random Trees, Springer, 2009.Google Scholar

[17] J.W., Moon, Counting Labelled Trees, Canadian Mathematical Monographs 1 (1970).Google Scholar

[18] A., Rényi, On the enumeration of trees, Combinatorial Structures and Their Applications, R., Guy, H., Hanani, N., Sauer, and J., Schonheim (Eds), Gordon and Breach, New York, 1970, 355–360.Google Scholar

[19] C., McDiarmid, A., Steger, and D., Welsh, Random graphs from planar and other addable classes, Topics in Discrete Mathematics, M., Klazar, J., Kratochvil, M., Loebl, J., Matousek, R., Thomas, and P., Valtr (Eds), Algorithms and Combinatorics 26. Springer, 2006, 231–246.Google Scholar

[20] P., Balister, B., Bollobás, and S., Gerke, Connectivity of addable graph classes, J. Combin. Theory B, 98 (2008), 577–584.Google Scholar

[21] P., Balister, B., Bollobás, and S., Gerke, Connectivity of random addable graphs, Proc. ICDM 2008, 13 (2010), 127–134.Google Scholar

[22] L., Addario-Berry, C., McDiarmid, and B., Reed, Connectivity for bridge-addable monotone graph classes, Combin. Prob. Comput., 21 (2012), 803–815.Google Scholar

[23] M., Kang and K., Panagiotou, On the connectivity of random graphs from addable classes, J. Combin. Theory B, 103 (2013), 306–312.Google Scholar

[24] G., Chapuy and G., Perarnau, Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture, arXiv:1238952 [math.CO] April 2015.CrossRef Google Scholar

[25] C., McDiarmid, Random graphs on surfaces, J. Combin. Theory B, 98 (2008), 778–797.Google Scholar

[26] C., McDiarmid, Connectivity for random graphs from a weighted bridge-addable class, Electronic J. Combin., 19(4) (2012), P53.Google Scholar

[27] O., Bernardi, M., Noy, and D., Welsh, Growth constants of minor-closed classes of graphs, J. Combin. Theory B, 100 (2010), 468–484.Google Scholar

[28] C., McDiarmid, Random graphs from a minor-closed class, Combin. Prob. Comput., 18 (2009), 583–599.Google Scholar

[29] J.H. van, Lint and R.M., Wilson, A Course in Combinatorics, 2nd edn., Cambridge University Press, Cambridge, 2001.Google Scholar

[30] N., Robertson, D., Sanders, P.D., Seymour, and R., Thomas, The four-color theorem, J. Combin. Theory B, 70 (1997), 2–44.Google Scholar

[31] P.D., Seymour, Hadwiger's Conjecture, manuscript, 2015.Google Scholar

[32] O., Giménez and M., Noy, Counting planar graphs and related families of graphs, in Surveys in Combinatorics 2009, 169–329, Cambridge University Press, Cambridge, 2009.Google Scholar

[33] N., Bonichon, C., Gavoille, N., Hanusse, D., Poulalhon, and G., Schaeffer, Planar graphs, via well-orderly maps and trees, Graphs Combin., 22 (2) (2006), 185–202.Google Scholar

[34] E.A., Bender, E.R., Canfield, and L.B., Richmond, Coefficients of functional compositions often grow smoothly, Electron. J. Combin., 15 (2008), #R21.Google Scholar

[35] M., Bousquet-Mélou and K., Weller, Asymptotic properties of some minor-closed classes of graphs, Combin. Prob. Comput., 23 (5) (2014), 749–795.Google Scholar

[36] M., Bodirsky, O., Giménez, M., Kang, and M., Noy, Enumeration and limit laws for series-parallel graphs, European Journal of Combinatorics, 28 (2007), 2091–2105.Google Scholar

[37] K., Weller, Connectivity and related properties for graph classes, DPhil thesis, Oxford University, 2013.Google Scholar

[38] C., McDiarmid, Random graphs from a weighted minor-closed class, Electronic J. Combin., 20 (2) (2013), P52, 39 pages.Google Scholar

[39] M., Kang and C., McDiarmid, Random unlabelled graphs containing few disjoint cycles, Random Structures Algorithms, 38 (2011), 174–204.Google Scholar

[40] V., Kurauskas and C., McDiarmid, Random graphs with few disjoint cycles, Combin. Prob. Comput., 20 (2011), 763–775.Google Scholar

[41] V., Kurauskas and C., McDiarmid, Random graphs containing few disjoint excluded minors, Random Structures Algorithms, 44 (2) (2014), 240–268.Google Scholar

[42] C., McDiarmid, On graphs with few disjoint t-star minors, European J. Combin., 32 (2011), 1394–1406.Google Scholar

[43] V., Kurauskas, On graphs containing few disjoint excluded minors, asymptotic number and structure of graphs containing few disjoint minors K4, arXiv: 1504.08107v1 [math.CO] 2015.Google Scholar