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 Wood that asks whether the number of cliques in n-vertex graphs with no K-t-minor is at most 2(ct)n for some constant c.