Densities of minor-closed graph classes are rational

MaRDI QIDQ6350063zbMATH OpenFDO

Authors Rohan Kapadia, Serguei Norine

Publication date 28 September 2020

Abstract: For a graph class $mathcalF$, let $e{x}_{mathcalF}(n)$ denote the maximum number of edges in a graph in $mathcalF$ on $n$ vertices. We show that for every proper minor-closed graph class $mathcalF$ the function $e{x}_{mathcalF}(n)-Deltan$ is eventually periodic, where $Delta=li{m}_{noinfty}e{x}_{mathcalF}(n)/n$ is the limiting density of $mathcalF$. This confirms a special case of a conjecture by Geelen, Gerards and Whittle. In particular, the limiting density of every proper minor-closed graph class is rational, which answers a question of Eppstein. As a major step in the proof we show that every proper minor-closed graph class contains a subclass of bounded pathwidth with the same limiting density, confirming a conjecture of the second author. Finally, we investigate the set of limiting densities of classes of graphs closed under taking topological minors.

This page was built for publication: Densities of minor-closed graph classes are rational

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350063)