On the maximum number of cliques in a graph embedded in a surface
This paper studies the following question: given a surface σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(n-ω)+2 ω and 8n+5/2 2 ω+o(2 ω), where ω is the maximum integer such that the complete graph K ω embeds in σ. For the surfaces S 0, S 1, S 2, N 1, N 2, N 3 and N 4 we establish an exact answer.
|Journal||European Journal of Combinatorics|
Dujmović, V, Fijavž, G. (Gaper), Joret, G. (Gwenaël), Sulanke, T. (Thom), & Wood, D. (2011). On the maximum number of cliques in a graph embedded in a surface. European Journal of Combinatorics, 32(8), 1244–1252. doi:10.1016/j.ejc.2011.04.001