Maximum degree in minor-closed classes of graphs. (July 2016) - Giménez, Omer; Mitsche, Dieter; Noy, Marc
Abstract: Given a class of graphs G closed under taking minors, we study the maximum degree Δ 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 Δ n not observed before, such us log n / log log log n and log n / log log log log n .