Small families under subdivision

Abstract

Let $H$ be a graph with maximum degree $d$, and let $d^{\prime }\ge 0$. We show that for some $c>0$ depending on $H,d^{\prime }$, and all integers $n\ge 0$, there are at most $c^n$ unlabelled simple $d$-connected $n$-vertex graphs with maximum degree at most $d^{\prime }$ that do not contain $H$ as a subdivision. On the other hand, the number of unlabelled simple $(d-1)$-connected $n$-vertex graphs with minimum degree $d$ and maximum degree at most $d+1$ that do not contain $K_{d+1}$ as a subdivision is superexponential in $n$.

Cited by in corpus (1)

• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three