Complete subgraphs in multipartite graphs

Details Complete subgraphs in multipartite graphs Complete subgraphs in multipartite graphs

2009-10-08

arxiv.org/abs/0910.1447v1

Mathematics

Combinatorics

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Complete subgraphs in multipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complete subgraphs in multipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complete subgraphs in multipartite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352661