# Extremal Graph Theory

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

- Turán number for complete balanced bipartite graphs (Zarankiewicz, not Erdős)
- Lower bound for Turán number for \(K_{4,4}\)
- Upper bound for Turán number for bipartite degenerate graphs (Simonovits) ($100)
- Lower bound for Turán number for bipartite non-degenerate graphs
- Turán number for bipartite graphs is a rational power of n (Simonovits)
- Turán number for even cycles (Simonovits)
- Turán number for families of graphs behave like Turán number for one of the members (Simonovits)
- Asymptotic behavior for joint Turán number for \(3\)- and \(4\)-cycles (Simonovits)
- Asymptotic behavior for joint Turán number for consecutive cycles (Simonovits)
- Extremal graph avoiding \(3\)- and \(4\)-cycles avoids all odd cycles
- Behavior of Turán number for a family of graphs is controlled by a bipartite member
- Turán number for cubes (Simonovits)
- Turán number for graphs with subgraphs of minimum degree \(> 2\) (Simonovits) ($250/$100)
- Number of edges in a graph with small independent sets avoid the octahedron (Hajnal, Sós, Szemerédi)
- Subgraphs of the cube without a \(2k\)-cycle ($100)
- Number of edges to force all trees (Sós)
- The \( (n/2-n/2-n/2) \) conjecture (Füredi, Loebl, Sós)
- Making a triangle-free graph bipartite (Faudree, Pach, Spencer)
- Largest bipartite subgraph of a triangle free graph
- \(2\)-coloring \(K_4\)-free graphs to avoid monochromatic triangles ($100) (Proven by Linyuan Lu in "Explicit construction of small Folkman graphs", 2008)
- Forcing triangles with local edge densities (Rousseau)
- Graphs covered by triangles (Rothschild)
- Edge-partitioning into paths (Gallai)
- Forcing large directed paths or independent sets (Rado)
- Minimizing the harmonic sum of cycle lengths (Hajnal)
- Subgraphs where every pair of edges is in a short cycle (Duke, Rödl) (two problems combined)
- Many edges are contained in \(5\)-cycles
- Decomposing a complete graph to avoid small odd cycles (Graham)
- Existence of Cycles of Order \(2^k\) (Gyárfás)
- Estimate the clique transversal number of a graph (Gallai, Tuza)
- Upper bound on clique transversal number
- Clique transversal number is sublinear for graphs with no small cliques
- Diameter of a \(K_r\)-free graph (Pach, Pollack, Tuza)
- Linearly many edges force certain cycle lengths ($100)
- Unions of bipartite graphs and graphs with bounded degree
- A problem on sparse induced subgraphs
- Any graph with many large independent sets is almost bipartite
- Upper bound for \(rt(n, 4; n/log(n))\)
- If \(G\) has no \(5\)-cliques, and any large subset of vertices contains a triangle, then \(G\) is sparse
- A graph without induced \(5\)-cycles has large cliques or independent sets