Complete subgraphs in multipartite graphs

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_{l}^{k}

, such that every

e l l

-partite graph whose parts have pairwise edge density greater than

d_{l}^{k}

contains a

K^{k}

. It turns out that

d_{l}^{k} = (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_{13}^{3} = 1 / 2

, disproving a conjecture by Bondy, Shen, Thomasse and Thomassen.

Recommendations

Cites Work

Cited In (16)

This page was built for publication: Complete subgraphs in multipartite graphs