On the critical densities of minor-closed classes

Colin McDiarmid; Michal Przykucki

doi:10.1016/j.ejc.2018.08.002

On the critical densities of minor-closed classes

Colin McDiarmid, Michal Przykucki

Mathematics

Research output: Contribution to journal › Article › peer-review

105 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	66-91
Number of pages	26
Journal	European Journal of Combinatorics
Volume	75
Early online date	9 Sept 2018
DOIs	https://doi.org/10.1016/j.ejc.2018.08.002
Publication status	Published - 1 Jan 2019

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2018.08.002Licence: None: All rights reserved

McDiarmid_&_Przykucki_On_the_critical_densities_European_Journal_of_Combinatorics_2018
Checked for eligibility: 12/09/2018
Accepted author manuscript, 410 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://www.sciencedirect.com/science/article/pii/S0195669818301367Licence: None: All rights reserved

Cite this

@article{826c70d8909847f09a4c6d9ba7f17021,

title = "On the critical densities of minor-closed classes",

abstract = "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 {\textquoteleft}asymptotically dense{\textquoteright}; and we answer some questions posed by Eppstein. ",

author = "Colin McDiarmid and Michal Przykucki",

year = "2019",

month = jan,

day = "1",

doi = "10.1016/j.ejc.2018.08.002",

language = "English",

volume = "75",

pages = "66--91",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Elsevier",

}

TY - JOUR

T1 - On the critical densities of minor-closed classes

AU - McDiarmid, Colin

AU - Przykucki, Michal

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053046363&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2018.08.002

DO - 10.1016/j.ejc.2018.08.002

M3 - Article

SN - 0195-6698

VL - 75

SP - 66

EP - 91

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

On the critical densities of minor-closed classes

Abstract

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this