Cliques in graphs excluding a complete graph minor

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

This paper considers the following question: What is the maximum number of k-cliques in an n-vertex graph with no Kt-minor? This question generalises the extremal function for Kt-minors, which corresponds to the k = 2 case. The exact answer is given for t ≤ 9 and all values of k. We also determine the maximum total number of cliques in an n-vertex graph with no Kt-minor for t ≤ 9. Several observations are made about the case of general t.

Original languageEnglish
Article numberP3.18
Number of pages16
JournalElectronic Journal of Combinatorics
Volume23
Issue number3
Publication statusPublished - 5 Aug 2016

Keywords

  • Clique
  • Graph theory
  • Minor

Cite this