Minor Clique Free Extremal Graphs

Abstract

In this note, we prove that the largest non-contractible to \(K^p\) graph of order \(n\) with \(\lceil \frac{2n+3}{3} \rceil \leq p \leq n\) is the Turán’s graph \(T_{2p-n-1}(n)\). Furthermore, a new upper bound for this problem is determined.