pith. machine review for the scientific record. sign in

arxiv: 0906.4142 · v3 · submitted 2009-06-22 · 🧮 math.CO

Recognition: unknown

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

Authors on Pith no claims yet
classification 🧮 math.CO
keywords mathbbomegagraphmaximumsigmaanswercliquesinteger
0
0 comments X
read the original 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/2} 2^{\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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.