Number of triangles in a multi-partite graph with large minimum degree
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A problem on the number of triangles in a multi-partite graph with large minimum degree (proposed by Bollobás, Erdös and Szemerédi [3])
Suppose \( G\) is an \(r \)-partite graph with vertex set consisting of \(r\) parts each of size \(n\). If the minimum degree of \(G\) is at least \(n+t\), is it true that \(G\) always contains \(4t^3\) triangles?In [3] was shown that such \( G\) contains \( t^3\) triangles, but does not have to contain more than \( 4t^3\) triangles.
Bibliography | |
---|---|
1 | A. Thomason, A disproof of a conjecture of Erdös in Ramsey theory, J. London Math. Soc. 39 (1989), 246-255. |
2 | F. Franek and V. Rödl, \( 2\)-colorings of complete graphs with a small number of monochromatic \( K_4\) subgraphs, Discrete Math. 114 (1993), 199-203. |
3 | B. Bollobás, P. Erdös and E. Szemerédi, On complete subgraphs of \( r\)-chromatic graphs, Discrete Math. 13 (1975), 97-107. |