New answers tagged

1 vote

Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

Say $\gamma(G)$ is the genus of a graph $G$. If $G$ has components $G_1,\dots,G_c$ then $\gamma(G)=\sum_{i=1}^c \gamma(G_i)$. This property is called the additivity of genus (and much stronger results ...
David Wood's user avatar
  • 1,243
5 votes

Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

Yes, this is true. See my paper Subgraph densities in a surface with Gwenaƫl Joret and David Wood. We prove that for every $s \geq 5$, the number of $s$-cliques in a graph of Euler genus $g$ is at ...
Tony Huynh's user avatar
  • 31.5k

Top 50 recent answers are included