Minors in Random Regular Graphs

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


We show that there is a constant c so that for fixed r >= 3 a.a.s. an r-regular graph on n vertices contains a complete graph on c root n vertices as a minor. This confirms a conjecture of Markstrom (Ars Combinatoria 70 (2004) 289-295). Since any minor of an r-regular graph on n vertices has at most m/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph G,,,p during the phase transition (i.e., when pn -> 1). (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 444-463, 2009
Original languageEnglish
Pages (from-to)444-463
Number of pages20
JournalRandom Structures and Algorithms
Issue number4
Publication statusPublished - 1 Dec 2009


  • Hadwiger number
  • random regular graphs
  • graph minors


Dive into the research topics of 'Minors in Random Regular Graphs'. Together they form a unique fingerprint.

Cite this