Complete subgraphs in multipartite graphs

DOI10.1007/S00493-012-2425-5MaRDI QIDQ2392040zbMATH OpenOpenAlexFDO

Authors Florian Pfender

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.1447

zbMATH Keywords

edge densityextremal graphsmultipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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 $ell$-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.

Review text

For large \(l\), the author finds the minimal edge density \(d(k,l)\) such that every \(l\)-partite graph whose parts have pairwise edge density greater than \(d(k,l)\) contains a \(k\)-complete graph. The structure of the extremal graphs is also described.

Recommendations

• Complete subgraphs in a multipartite graph
• Complete Subgraphs of r-partite Graphs
• On Subgraphs of the Complete Bipartite Graph
• Complete partitions of graphs
• Complete partitions of graphs
• Complete partite subgraphs in dense hypergraphs
• Complete multipartite graphs and their null set
• scientific article; zbMATH DE number 4008444
• Integral complete multipartite graphs
• Integral complete multipartite graphs

Cites work

• Density conditions for triangles in multipartite graphs
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)

Cited in

(18)

• Complete \(r\)-partite subgraphs of dense \(r\)-graphs
• Induced complete \(h\)-partite graphs in dense clique-less graphs
• Subgraph complementation
• Complete multipartite graphs and Braess edges
• Semicomplete Multipartite Digraphs
• Long paths and connectivity in 1-independent random graphs
• scientific article; zbMATH DE number 4008444 (Why is no real title available?)
• scientific article; zbMATH DE number 3520443 (Why is no real title available?)
• scientific article; zbMATH DE number 1076140 (Why is no real title available?)
• A Density Turán Theorem
• A multipartite version of the Turan problem - density conditions and eigenvalues
• On the complete subgraphs of graphs defined by systems of sets
• Complete subgraphs in a multipartite graph
• On connectivity in random graph models with limited dependencies
• On density conditions for transversal trees in multipartite graphs
• A neighborhood condition which implies the existence of a complete multipartite subgraph
• A stability theorem for multi-partite graphs
• Density conditions for triangles in multipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392040)