Number of pentagons in a triangle free graph
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
Problem [1]
Is it true that a triangle-free graph on \(5n\) vertices can contain at most \(n^5\) pentagons?Györi \( ^{[2]}\) proved that such graph can have at most \( 3^3 5^4 / 2^{14}~ n^5 \approx 1.03 n^5\) triangles.
Bibliography | |
---|---|
1 | P. Erdös, On some problems in graph theory, combinatorial analysis and combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1-17, Academic Press, London-New York, 1984. |
2 |
E. Györi, On the number of \( C_5\)'s in a triangle-free graph,
Combinatorica 9 (1989), 101-102.
|