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 Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2016 - 2:09:53 PM
Last modification on : Saturday, June 25, 2022 - 11:18:57 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

21

Files downloads

46