Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777613 | Journal of Combinatorial Theory, Series B | 2017 | 23 Pages |
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 Kt-minor has at most c(t)n cliques. Wood asked in 2007 if we can take c(t)=ct 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 Kt-minor has at most 32t/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â¡(32t/3âx/3+o(t)n,2t+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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jacob Fox, Fan Wei,