Turán number for graphs with subgraphs of minimum degree \(> 2\)
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
For a finite family \( {\mathcal F}\) of graphs, let \( t(n, {\mathcal{F}})\) denote the smallest integer \( m\) that every graph on \( n\) vertices and \( m\) edges must contain a member of \( \mathcal{F}\) as a subgraph.
A problem on Turán numbers for graphs with degree constraints} (proposed by Erdös and Simonovits [1]. $250 for a proof and $100 for a counterexample)
Prove or disprove that \[ t(n,H) =O( n^{3/2}) \] if and only if \(H\) does not contain a subgraph each vertex of which has degree \(>2\).
Bibliography  

1 
P. Erdös, Some of my old and new combinatorial problems, Paths, flows, and VLSIlayout (Bonn, 1988), Algorithms Combin., 9,
3545, Springer, Berlin, 1990.
