On the number of cliques in graphs with a forbidden minor

DOI10.1016/J.JCTB.2017.04.004MaRDI QIDQ2399355zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Fan Wei

Publication date 22 August 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07056

zbMATH Keywords

forbidden minorscontainer methodHadwiger numbercounting cliques

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Graph minors (05C83)

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 $ngeq4t/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 $ngeqmax(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.

Recommendations

• Cliques in graphs excluding a complete graph minor
• Number of cliques in graphs with a forbidden subdivision
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Clique minors in graphs with a forbidden subgraph
• Independent sets in graphs with an excluded clique minor

Cites work

• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A linear-time algorithm to find a separator in a graph excluding a minor
• An extremal function for contractions of graphs
• Cliques in graphs excluding a complete graph minor
• Graph minors. XX: Wagner's conjecture
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphiesätze für Graphen
• Lower bound of the Hadwiger number of graphs by their average degree
• Number of cliques in graphs with a forbidden subdivision
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• On the maximum number of cliques in a graph
• On the number of graphs without 4-cycles
• Proper minor-closed families are small
• Rank-width and tree-width of \(H\)-minor-free graphs
• Some Theorems on Abstract Graphs
• Testing first-order properties for subclasses of sparse graphs
• The extremal function for complete minors

Cited in

(12)

• Finding cliques in social networks: a new distribution-free model
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• The maximum number of pentagons in a planar graph
• Finding cliques in social networks: a new distribution-free model
• Tree densities in sparse graph classes
• Phase transition of degeneracy in minor-closed families
• Counting cliques in 1-planar graphs
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Cliques in graphs excluding a complete graph minor
• Subgraph densities in a surface
• The maximum number of paths of length three in a planar graph
• Number of cliques in graphs with a forbidden subdivision

This page was built for publication: On the number of cliques in graphs with a forbidden minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399355)