Loading...
Loading...

Go to the content (press return)

Maximum degree in minor-closed classes of graphs

Author
Giménez, O.; Mitsche, D.; Noy, M.
Type of activity
Journal article
Journal
European journal of combinatorics
Date of publication
2016-07-01
Volume
55
First page
41
Last page
61
DOI
https://doi.org/10.1016/j.ejc.2016.02.001 Open in new window
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. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords
random tree
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants