On the number of cliques in graphs with a forbidden minor

DOI10.1016/J.JCTB.2017.04.004zbMATH Open1368.05110arXiv1603.07056OpenAlexW2963779710MaRDI QIDQ2399355FDOQ2399355

Authors: Jacob Fox, Fan Wei 

Publication date: 22 August 2017

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

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.

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

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

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)

Cites Work

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

Cited In (12)

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

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)