Number of cliques in graphs with a forbidden subdivision

Abstract

We prove that for all positive integers $t$, every $n$-vertex graph with no $K_t$-subdivision has at most $2^{50t}n$ cliques. We also prove that asymptotically, such graphs contain at most $2^{(5+o(1))t}n$ cliques, where $o(1)$ tends to zero as $t$ tends to infinity. This strongly answers a question of D. Wood asking if the number of cliques in $n$-vertex graphs with no $K_t$-minor is at most $2^{ct}n$ for some constant $c$.

10 pages; to appear in SIAM J. Discrete Math

References in corpus (3)

• Rank-width and Tree-width of H-minor-free Graphs
• The maximum number of cliques in a graph embedded in a surface
• Cliques in Odd-Minor-Free Graphs

Cited by in corpus (3)

• Rank-width: Algorithmic and structural results
• Subgraph densities in a surface
• Tree densities in sparse graph classes