ACO The ACO Seminar (2014–2015)

Feb. 5, 3:30pm, Wean 8220
Sergey Norin, McGill University
Densities of minor-closed families of graphs


The density of a sparse family of graphs is defined as the supremum of the ratio of the number of edges to the number of vertices over graphs in the family. For example, the density of forests is one, and the density of planar graphs is three. Eppstein has recently initiated a systematic study of the set of possible densities of minor-closed graph families. We answer one of his questions, showing that all such densities are rational.

Based on joint work with Rohan Kapadia.

Back to the ACO home page