Cliques in graphs excluding a complete graph minor

zbMath1344.05132arXiv1511.04655MaRDI QIDQ311514

David R. Wood

Publication date: 13 September 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph minorclique

Mathematics Subject Classification ID

Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets in graphs with given minimum degree
• Extremal problems for independent set enumeration
• Two problems on independent sets in graphs
• On the maximum number of cliques in a graph embedded in a surface
• Rank-width and tree-width of \(H\)-minor-free graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• A Kruskal-Katona type theorem for graphs
• On the maximum number of cliques in a graph
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• On the maximum density of graphs which have no subcontraction to \(K^ r\).
• Hadwiger's conjecture is true for almost every graph
• On minimal Eulerian graphs
• The maximum number of triangles in a \(K_4\)-free graph
• A new Turán-type theorem for cliques in graphs
• The extremal function for complete minors
• Counting cycles and finite dimensional \(L^{p}\) norms
• On the number of cliques in graphs with a forbidden minor
• The maximum number of complete subgraphs in a graph with given maximum degree
• The extremal function for \(K_{9}\) minors
• Proper minor-closed families are small
• Homomorphiesätze für Graphen
• Homomorphism theorems for graphs
• A linear-time algorithm to find a separator in a graph excluding a minor
• An extremal function for contractions of graphs
• Number of Cliques in Graphs with a Forbidden Subdivision
• Cliques in random graphs
• On the number of cycles of lengthk in a maximal planar graph
• Contractions to k₈
• Maximizing the Number of Independent Sets of a Fixed Size
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion

Related Items (12)

Subgraph densities in a surface ⋮ On the number of cliques in graphs with a forbidden minor ⋮ The maximum number of paths of length three in a planar graph ⋮ Excluding infinite clique minors ⋮ Phase transition of degeneracy in minor-closed families ⋮ Product structure of graph classes with bounded treewidth ⋮ Packing and covering balls in graphs excluding a minor ⋮ The maximum number of pentagons in a planar graph ⋮ Tutte embeddings of tetrahedral meshes ⋮ Excluded minors in cubic graphs ⋮ Excluding a countable clique ⋮ Counting cliques in 1-planar graphs

This page was built for publication: Cliques in graphs excluding a complete graph minor