2019/10/10 by Maria Chudnovsky, Chudnovsky, Maria, Martin Loebl +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1910.04609
arxiv created 2019/10/10 · arxiv updated 2019/10/11
Let H be a graph with maximum degree d, and let d'≥ 0. We show that for some c>0 depending on H,d', and all integers n≥ 0, there are at most cn 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 Kd+1 as a subdivision is superexponential in n.