pith. sign in

arxiv: 1407.7707 · v5 · pith:WRYJNVFTnew · submitted 2014-07-29 · 🧮 math.CO

Number of cliques in graphs with a forbidden subdivision

classification 🧮 math.CO
keywords cliquesgraphsnumberprovesubdivisiontendsvertexanswers
0
0 comments X
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.