The maximum number of cliques in a graph embedded in a surface

Abstract

This paper studies the following question: Given a surface $\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\Sigma$? We characterise the extremal graphs for this question, and prove that the answer is between $8(n-\omega )+2^{\omega }$ and $8n+3/22^{\omega }+o(2^{\omega })$, where $\omega$ is the maximum integer such that the complete graph $K_{\omega }$ embeds in $\Sigma$. For the surfaces ${\mathbb{S}}_0$, ${\mathbb{S}}_1$, ${\mathbb{S}}_2$, ${\mathbb{N}}_1$, ${\mathbb{N}}_2$, ${\mathbb{N}}_3$ and ${\mathbb{N}}_4$ we establish an exact answer.

References in corpus (4)

• Rank-width and Tree-width of H-minor-free Graphs
• Irreducible triangulations of low genus surfaces
• Generating irreducible triangulations of surfaces
• Irreducible Triangulations are Small

Cited by in corpus (7)

• Rank-width and Tree-width of H-minor-free Graphs
• Subgraph densities in a surface
• Tree densities in sparse graph classes
• Number of cliques in graphs with a forbidden subdivision
• Homomorphism counts in robustly sparse graphs
• Cliques in Odd-Minor-Free Graphs
• A fast algorithm for computing irreducible triangulations of closed surfaces in $E^d$