Graphs covered by triangles
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 graphs covered by triangles (proposed by Erdös and Rothschild [1])
Suppose \(G\) is a graph of \(n\) vertices and \(e=cn^2\) edges. Assume that every edge of \(G\) is contained in at least one triangle. Determine the largest integer \(m=f(n,c)\) such that in every such graph there is an edge contained in at least \(m\) triangles.Alon and Trotter showed that \( f(n,c) < \alpha_c \sqrt n\) (personal communication). In the other direction [1], Szemerédi observed that the regularity lemma implies that \( f(n,c)\) approaches infinity for every fixed \( c\). Is it true that \( f(n,c) > n^{\epsilon}\)?
Bibliography  

1 
P. Erdös, Some problems on finite and infinite graphs, Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math. 65,
223228, Amer. Math. Soc., Providence, R. I., 1987.
