On the maximum number of cliques in a graph embedded in a surface

DOI10.1016/j.ejc.2011.04.001zbMath1229.05139arXiv0906.4142MaRDI QIDQ648982

David R. Wood, Gašper Fijavž, Vida Dujmović, Thom Sulanke, Gwenaël Joret

Publication date: 29 November 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

maximum number of cliques

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

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

Related Items

Unnamed Item, Tree densities in sparse graph classes, Finding Cliques in Social Networks: A New Distribution-Free Model, Subgraph densities in a surface, Cliques in graphs excluding a complete graph minor, Irreducible triangulations are small, A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\), Counting cliques in 1-planar graphs, Number of Cliques in Graphs with a Forbidden Subdivision

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• All 2-manifolds have finitely many minimal triangulations
• Rank-width and tree-width of \(H\)-minor-free graphs
• Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann
• Note on the irreducible triangulations of the Klein bottle
• Irreducible triangulations are small
• On the maximum number of cliques in a graph
• Minimal triangulations on orientable surfaces
• The maximum number of triangles in a \(K_4\)-free graph
• Irreducible triangulations of the Klein bottle
• Hierarchy of surface models and irreducible triangulations.
• Generating the triangulations of the projective plane
• Proper minor-closed families are small
• A linear-time algorithm to find a separator in a graph excluding a minor
• Note on irreducible triangulations of surfaces