Number of cliques in graphs with a forbidden subdivision
classification
🧮 math.CO
keywords
cliquesgraphsnumberprovesubdivisiontendsvertexanswers
read the original 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.