Ramsey theory

1. (Problem not available) The Happy Ending problem: forcing convex polygons (Szekeres)
2. (Problem not available) Forcing empty convex polygons
3. (Problem not available) Does the Ramsey limit exist? What is the limit? ($100 / $250)
4. (Problem not available) Constructive Ramsey ($100)
5. (Problem not available) Lower bound for r(4, n) ($250)
6. (Problem not available) Lower bound for r(k, n)
7. (Problem not available) Consecutive Ramsey numbers (Burr)
8. (Problem not available) Bounds for growth of r(3, n) (Sós) (two problems combined)
9. (Problem not available) Linear Ramsey numbers (Burr) ($25 according to errata) (three problems combined)
10. (Problem not available) Cliques are Ramsey-extremal (Graham)
11. (Problem not available) r(G) is subexponential in sqrt(edges)
12. (Problem not available) r(G) is bounded by r(Chi(G)) (1)
13. (Problem not available) r(G) is bounded by r(Chi(G)) (2)
14. (Problem not available) Upper bound for Ramsey on trees (Burr) (Potentially helpful article)
15. (Problem not available) Exact Ramsey value for some trees
16. (Problem not available) Upper bound on r(tree, complete multi-partite)
17. (Problem not available) Upper bound for Ramsey number for 4-cycle (Progress has been made by Yusheng Li and Wenan Zang in JCT B 87 (2003) p 280-288)
18. (Problem not available) Exact values for Ramsey numbers for k-cycle (Faudree, Rousseau, Schelp) (three problems combined)
19. (Problem not available) Exact value for Ramsey number of k-cycle and star (Burr, Faudree, Rousseau, Schelp)
20. (Problem not available) Upper bound for Ramsey number for the hypercube (Burr) (Editor's note: A better bound is listed in the book.)
21. (Problem not available) Multi-color Ramsey number for triangles ($250/$100) (two problems combined)
22. (Problem not available) r(3, 3, n) is much larger than r(3, n) (Sós) (Proven by Noga Alon and Vojtech Rodl in Combinatorica 25 (2005) p 125-141)
23. (Problem not available) Multi-color Ramsey number for triangles grows faster than for other odd cycles (Graham)
    Related material: Upper bound on multicolor Ramsey number for odd cycles was found under regularity assumption by Yusheng Li in JGT 62 (2009) p 324-328.
    This bound is tight for 3-, 5-, and 9-cycles according to Yusheng Li and Ko-Wei Lih in European Journal of Combinatorics 30 (2009) p 114-118.
24. (Problem not available) Multi-color Ramsey number for even cycles (Graham)
25. (Problem not available) 3-color Ramsey number for n-cycles (Bondy)
26. (Problem not available) Multi-color Ramsey number for trees (Graham)
27. (Problem not available) Multi-color Ramsey number for complete bipartite graphs (Chung, Graham)
28. (Problem not available) Size Ramsey number for graphs of bounded degree (Beck)
29. (Problem not available) Size Ramsey number for complete balanced bipartite graphs (Faudree, Rousseau, Schelp)
30. (Problem not available) Size Ramsey number for unions of stars (Burr, Faudree, Rousseau, Schelp)
31. (Problem not available) A linear bound on some size Ramsey numbers (Faudree, Rousseau, Schelp)
32. (Problem not available) A linear bound on some size Ramsey numbers for particular graphs (Faudree, Rousseau, Schelp)
33. (Problem not available) A linear bound on some size Ramsey numbers for trees (Faudree, Rousseau, Schelp)
34. (Problem not available) A linear bound on some size Ramsey numbers for odd cycles (Faudree, Rousseau, Schelp)
35. (Problem not available) A linear bound on some size Ramsey numbers for cycles (Faudree, Rousseau, Schelp)
36. (Problem not available) Upper bound on induced Ramsey numbers (Rödl)
37. (Problem not available) Double exponential lower bound for 3-uniform hypergraph Ramsey numbers (Hajnal, Rado) ($500)
38. (Problem not available) Asymptotic behavior of t-uniform hypergraph Ramsey numbers (Hajnal, Rado)
39. (Problem not available) Asymptotic behavior of generalized Ramsey numbers
40. (Problem not available) Behavior of generalized hypergraph Ramsey numbers ($500)

Extremal graph theory

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

Coloring, packing and covering

1. (Problem not available) Growth of girth in graphs with fixed chromatic number
2. (Problem not available) Counting vertices of a graph with large girth and chromatic number
3. (Problem not available) Finding subgraphs with large girth and chromatic number (Hajnal)
4. (Problem not available) Ratio of chromatic number to clique number
5. (Problem not available) Decomposing graphs into subgraphs with higher total chromatic number (Lovász)
6. (Problem not available) Bipartite graphs with high list-chromatic numbers
7. (Problem not available) If G is (a, b)-choosable, then G is (am, bm)-choosable for every positive integer m (Rubin, Taylor)
8. (Problem not available) List-coloring unions of graphs
9. (Problem not available) Estimate the maximum number of edges for a k-critical graph on n vertices
10. (Problem not available) Find the exact maximum number of edges for a k-critical graph on n vertices
11. (Problem not available) Critical graphs with large minimum degree
12. (Problem not available) Vertex critical graphs with many extra edges
13. (Problem not available) Bounding the strong chromatic index (Nešetřil)
14. (Problem not available) Many disjoint monochromatic triangles (Faudree, Ordman) (two problems combined)
15. (Problem not available) Edge-coloring to avoid large monochromatic stars (Faudree, Rousseau, Schelp)
16. (Problem not available) Anti-Ramsey graphs (Burr, Graham, Sós)
17. (Problem not available) Anti-Ramsey problem for balanced colorings
18. (Problem not available) Bounding the acyclic chromatic number for graphs of bounded degree
19. (Problem not available) Any graph of large chromatic number has an odd cycle spanning a subgraph of large chromatic number (Hajnal)
20. (Problem not available) Any graph of large chromatic number has many edge-disjoint cycles on one subset of vertices (Hajnal)
21. (Problem not available) Covering by 4-cycles
22. (Problem not available) Maximum chromatic number of the complement graph of graphs with fixed h(G) (Faudree)
23. (Problem not available) Ratio of clique partition number to clique covering number (Faudree, Ordman)
24. (Problem not available) Difference of clique partition number to clique covering number
25. (Problem not available) Maximum product of clique partition numbers for complementary graphs
26. (Problem not available) The ascending subgraph decomposition problem (Alavi, Boals, Chartrand, Oellermann)

Random graphs and graph enumeration

1. (Problem not available) At what density is the chromatic number of a random graph r?
2. (Problem not available) Find the range of expected chromatic numbers for a random graph
3. (Problem not available) Random graphs contain cubes (Bollobás)
4. (Problem not available) Large independent sets in all large subgraphs of a random graph (Bollobás)
5. (Problem not available) Covering a random graph with triangles (Spencer)
6. (Problem not available) Avoiding anti-monotone graph properties in a random graph (Suen, Winkler)
7. (Problem not available) Number of induced G-subgraphs in a given graph
8. (Problem not available) Adding an edge to an extremal 4-cycle-free graph gives two 4-cycles (Siminovits)
9. (Problem not available) Number of triangles in a multi-partite graph with large minimum degree (Bollobás, Szemerédi)
10. (Problem not available) Number of graphs with a forbidden subgraph (Kleitman, Rothschild)
11. (Problem not available) Regular induced subgraphs (Fajtlowicz, Staton)
12. (Problem not available) Graphs with induced subgraphs of any number of edges (McKay) ($100)
13. (Problem not available) Count the ways to add a K₄ (Tuza)
14. (Problem not available) Number of triangle-free graphs
15. (Problem not available) Number of pentagons in a triangle free graph
16. (Problem not available) F(n) = F(a) + F(b) + F(c) + F(d) + (a^-1 + b^-1 + c^-1 + d^-1)abcd (Sós)

Hypergraphs

1. (Problem not available) Turán's conjecture: hypergraph Turán numbers: t_r(n, k) (Turán, not Erdős) ($1000)
2. (Problem not available) Exact values for t₃(n, 4) (Turán, not Erdős) ($500)
3. (Problem not available) t₃(n, 5) (Turán, not Erdős)
4. (Problem not available) Adding an edge to extremal K⁽³⁾_k-free graph gives two copies of K⁽³⁾_k
5. (Problem not available) Adding an edge to extremal K⁽³⁾_k-free graph gives a K⁽³⁾_k+1 missing an edge
6. (Problem not available) Avoiding triple systems (Brown, Sós)
7. (Problem not available) Lower bound for hypergraph Turán numbers
8. (Problem not available) Turán densities are rational
9. (Problem not available) Unavoidable stars (Rado)
10. (Problem not available) Special case: unavoidable 3-stars
11. (Problem not available) Unavoidable stars of an n-set (Szemerédi)
12. (Problem not available) Weak Δ-systems (Milner, Rado)
13. (Problem not available) Weak Δ-systems of an n-set (Szemerédi)
14. (Problem not available) Erdős-Faber-Lovász conjecture: a simple hypergraph on n vertices has chromatic index at most n (Faber, Lovász)
15. (Problem not available) Minimum number of edges for a n-graph to not have Property B (that is: to not be 2-colorable)
16. (Problem not available) Minimum number of edges for a 3-chromatic 4-graph
17. (Problem not available) Conjecture on 3-chromatic hypergraphs (Lovász)
18. (Problem not available) Conjecture on minimum 3-chromatic hypergraphs (Lovász)
19. (Problem not available) Maximum edges in a 3-chromatic r-clique (Lovász)
20. (Problem not available) Maximum vertices in a 3-chromatic r-clique (Lovász)
21. (Problem not available) 3-chromatic cliques have edges with large intersection (Lovász) ($100)
22. (Problem not available) Number of sizes of edge intersections in a 3-chromatic r-graph (Lovász)
23. (Problem not available) Jumping densities for 3-hypergraphs ($500)
24. (Problem not available) Conjecture on covering a hypergraph (Lovász)
25. (Problem not available) Stronger conjecture on covering a hypergraph
26. (Problem not available) Maximum unavoidable hypergraphs (Chung)
27. (Problem not available) Unavoidable stars with fixed intersection size (Duke)
28. (Problem not available) Hypergraph decomposition (Chung, Graham)
29. (Problem not available) Characterize hypergraphs with maximum/minimum product of point and line covering numbers (Chung, Graham)
30. (Problem not available) Covering complete 3-graphs (Tuza)
31. (Problem not available) r-sets with common union and intersection (Füredi)
32. (Problem not available) Finding small global vertex covers for r-graphs with small local vertex covers (Fon der Flaass, Kostochka, Tuza)
33. (Problem not available) A Ramsey-type conjecture for 2-colorings of complete 3-graphs
34. (Problem not available) A Ramsey-Turán upper bound for 3-graphs
35. (Problem not available) A Ramsey-Turán lower bound for 3-graphs (Sós)

Infinite graphs

1. (Problem not available) Menger's theorem for infinite graphs
2. (Problem not available) Ordinal Ramsey: For which α does ω^α → (ω^α, 3)²? (Hajnal) ($1000)
3. (Problem not available) Ordinal Ramsey: If α → (α, 3)², then α → (α, 4)² (Hajnal)
4. (Problem not available) Ordinal Ramsey: ω₁ → (α, 4)³ for α < ω₁
5. (Problem not available) Ordinal Ramsey: ω₁² → (ω₁², 3)²
6. (Problem not available) Ordinal Ramsey: ω₃ → (ω₂ + 2)³_ω
7. (Problem not available) Almost-bipartite graphs with infinite chromatic number (Hajnal, Szemerédi) ($250)
8. (Problem not available) Another problem on almost-bipartite graphs with infinite chromatic number
9. (Problem not available) Uncountable-chromatic graphs have common 4-chromatic subgraphs (Hajnal)
10. (Problem not available) Infinite K₄-free graphs are the union of triangle-free countable graphs (Hajnal) ($250)
11. (Problem not available) The harmonic sums of odd-cycle lengths diverges for graphs of infinite chromatic number (Hajnal)
12. (Problem not available) There is an uncountable-chromatic graph G so that the size of the smallest n-chromatic subgraph grows arbitrarily slowly (Hajnal, Szemerédi)
13. (Problem not available) Infinite graphs have infinite paths or arbitrary independent sets (Hajnal, Milner)
14. (Problem not available) Down-up matchings in infinite graphs (Larson)