language-icon Old Web
English
Sign In

Small families under subdivision.

2019 
Let $H$ be a graph with maximum degree $d$, and let $d'\ge 0$. We show that for some $c>0$ depending on $H,d'$, 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'$ 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$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    9
    References
    2
    Citations
    NaN
    KQI
    []