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

DOI10.1016/j.ejc.2011.04.001zbMath1229.05139arXiv0906.4142OpenAlexW1985880617MaRDI 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

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

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

Cites Work

• 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
• Note on irreducible triangulations of surfaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the maximum number of cliques in a graph embedded in a surface