Extremal graph avoiding \(3\)- and \(4\)-cycles avoids all odd cycles
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. Simonovits [1] raised the following question:
Conjecture[1]
Prove that \[ t(n,\{C_{3},C_{4}\}) = t(n,\{C_{3},C_{4},C_5,C_7,C_9,C_{11},\ldots\}). \]
Bibliography | |
---|---|
1 | M. Simonovits,
Paul Erdös' influence on extremal graph theory,
The Mathematics of Paul Erdös, II (R. L. Graham and J.
Nešetril, eds.), 148-192, Springer-Verlag, Berlin, 1996.
|