On the maximum number of cliques in a graph

DOI10.1007/s00373-007-0738-8zbMath1122.05048arXivmath/0602191OpenAlexW3124913715MaRDI QIDQ995772

David R. Wood

Publication date: 10 September 2007

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph minordegeneracycliqueplanar graphextremal graph theoryTurán's theoremcomplete subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83)

Related Items

Medians in median graphs and their cube complexes in linear time ⋮ Subgraph densities in a surface ⋮ Tree densities in sparse graph classes ⋮ Number of Cliques in Graphs with a Forbidden Subdivision ⋮ An extended depth-first search algorithm for optimal triangulation of Bayesian networks ⋮ Cliques in graphs excluding a complete graph minor ⋮ Kernelization using structural parameters on sparse graph classes ⋮ On the number of cliques in graphs with a forbidden minor ⋮ Generalized planar Turán numbers ⋮ Homomorphisms into loop-threshold graphs ⋮ On supersaturation and stability for generalized Turán problems ⋮ The maximum number of paths of length three in a planar graph ⋮ Many triangles with few edges ⋮ The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ Planar graphs with the maximum number of induced 6-cycles ⋮ The maximum number of complete subgraphs in a graph with given maximum degree ⋮ The Hosoya index and the Merrifield-Simmons index ⋮ On the maximum number of cliques in a graph embedded in a surface ⋮ Independent sets in graphs ⋮ The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ A note on Turán's theorem ⋮ Unnamed Item ⋮ On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion ⋮ Local planar domination revisited ⋮ Counting cliques in 1-planar graphs ⋮ Supersaturation for subgraph counts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique graphs of packed graphs
• Bounds on the number of complete subgraphs
• On Hadwiger's number---A problem of the Nordhaus-Gaddum type
• On complete subgraphs of \(r\)-chromatic graphs
• The maximum number of q-cliques in a graph with no p-clique
• Limit theorems for complete subgraphs of random graphs
• A partial k-arboretum of graphs with bounded treewidth
• 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
• Proper minor-closed families are small
• A generalization of a theorem of Turán
• An extremal function for contractions of graphs
• Maximal independent sets in graphs with at mostr cycles
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• Lower bounds on the number of triangles in a graph
• On clique-extremal (p,q)-graphs
• Cliques in random graphs
• Connectivity, graph minors, and subgraph multiplicity
• An upper bound on the number of cliques in a graph
• On the Number of Complete Subgraphs of a Graph
• On the number of complete subgraphs and circuits contained in graphs
• On the number of complete subgraphs and circuits in a graph
• On cliques in graphs
• On cliques in graphs
• The number of maximum independent sets in graphs
• Ramsey-Turán theory
• On cliques in graphs