Extremal Graph Theory

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