Skip to Main content Skip to Navigation
Journal articles

Maximum degree in minor-closed classes of graphs

Abstract : Given a class of graphs G closed under taking minors, we study the maximum degree Delta_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Delta_n not observed before, such us log n/ log log log n and log n/ log log log log n.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01291968
Contributor : Dieter Mitsche <>
Submitted on : Tuesday, September 6, 2016 - 2:09:53 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM

File

maxdegree-RevisedVersionEurope...
Files produced by the author(s)

Identifiers

Collections

Citation

Omer Giménez, Dieter Mitsche, Marc Noy. Maximum degree in minor-closed classes of graphs. European Journal of Combinatorics, Elsevier, 2016, ⟨10.1016/j.ejc.2016.02.001⟩. ⟨hal-01291968⟩

Share

Metrics

Record views

108

Files downloads

205