pith. sign in

arxiv: 0910.1447 · v1 · submitted 2009-10-08 · 🧮 math.CO

Complete subgraphs in multipartite graphs

classification 🧮 math.CO
keywords graphsdensityedgegraphcompletecontainseveryextremal
0
0 comments X
read the original abstract

Turan's Theorem states that every graph of a certain edge density contains a complete graph $K^k$ and describes the unique extremal graphs. We give a similar Theorem for l-partite graphs. For large l, we find the minimal edge density $d^k_l$, such that every $\ell$-partite graph whose parts have pairwise edge density greater than $d^k_l$ contains a $K^k$. It turns out that $d^k_l=(k-2)/(k-1)$ for large enough l. We also describe the structure of the extremal graphs. For the case of triangles we show that $d^3_{13}=1/2$, disproving a conjecture by Bondy, Shen, Thomasse and Thomassen.

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.