Maximum degree in minor-closed classes of graphs. (July 2016)

• Record Type: Journal Article
• Authors: Giménez, Omer; Mitsche, Dieter; Noy, Marc
• Is Part Of: European journal of combinatorics. Volume 55(2016:Jul.)
• Page Start: 41
• Page End: 61
• Publication Date: 2016-07
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.02.001
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .