## Abstract

Reed and Wood and independently Norine, Seymour, Thomas, and Wollan proved that for each positive integer t there is a constant c(t) such that every graph on n vertices with no K_{t}-minor has at most c(t)n cliques. Wood asked in 2007 if we can take c(t)=c^{t} for some absolute constant c. This question was recently answered affirmatively by Lee and Oum. In this paper, we determine the exponential constant. We prove that every graph on n vertices with no K_{t}-minor has at most 3^{2t/3+o(t)}n cliques. This bound is tight for n≥4t/3. More generally, let H be a connected graph on t vertices, and x denote the size (i.e., the number edges) of the largest matching in the complement of H. We prove that every graph on n vertices with no H-minor has at most max(3^{2t/3−x/3+o(t)}n,2^{t+o(t)}n) cliques, and this bound is tight for n≥max(4t/3−2x/3,t) by a simple construction. Even more generally, we determine explicitly the exponential constant for the maximum number of cliques an n-vertex graph can have in a minor-closed family of graphs which is closed under disjoint union.

Original language | English (US) |
---|---|

Pages (from-to) | 175-197 |

Number of pages | 23 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 126 |

DOIs | |

State | Published - Sep 2017 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Container method
- Counting cliques
- Forbidden minors
- Hadwiger number