On the critical densities of minor-closed classes

Given a minor-closed class A of graphs, let βA denote the supremum over all graphs in A of the ratio of edges to vertices. We investigate the set B of all such values βA, taking further the project begun by Eppstein. Amongst other results, we determine the small values in B (those up to 2); we show...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2019-01, Vol.75, p.66-91
Main Authors: McDiarmid, Colin, Przykucki, Michał
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a minor-closed class A of graphs, let βA denote the supremum over all graphs in A of the ratio of edges to vertices. We investigate the set B of all such values βA, taking further the project begun by Eppstein. Amongst other results, we determine the small values in B (those up to 2); we show that B is ‘asymptotically dense’; and we answer some questions posed by Eppstein.
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2018.08.002