All Problems
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

Ramsey Theory
 The Happy Ending problem: forcing convex polygons (Szekeres)
 Forcing empty convex polygons
 Does the Ramsey limit exist? What is the limit? ($100 / $250)
 Constructive Ramsey ($100)
 Lower bound for \( r(4, n) \) ($250)
 Lower bound for \(r(k, n)\)
 Consecutive Ramsey numbers (Burr)
 Bounds for growth of \(r(3, n)\) (Sós) (two problems combined)
 Linear Ramsey numbers (Burr) ($25)
 Cliques are Ramseyextremal (Graham)
 \(r(G)\) is subexponential in sqrt(edges)
 \(r(G)\) is bounded by \(r(\chi(G))\) (1)
 \(r(G)\) is bounded by \(r(\chi(G))\) (2)
 Upper bound for Ramsey on trees (Burr)
 Exact Ramsey value for some trees
 Upper bound on r(tree, complete multipartite)
 Upper bound for Ramsey number for \(4\)cycle
 Exact values for Ramsey numbers for \(k\)cycle (Faudree, Rousseau, Schelp)
 Exact value for Ramsey number of \(k\)cycle and star (Burr, Faudree, Rousseau, Schelp)
 Upper bound for Ramsey number for the hypercube (Burr)
 Multicolor Ramsey number for triangles ($250/$100)
 \(r(3, 3, n)\) is much larger than \(r(3, n)\)

Multicolor Ramsey number for triangles grows faster than for other odd cycles (Graham)
 Multicolor Ramsey number for even cycles (Graham)
 \(3\)color Ramsey number for \(n\)cycles (Bondy)
 Multicolor Ramsey number for trees (Graham)
 Multicolor Ramsey number for complete bipartite graphs (Chung, Graham)
 Size Ramsey number for graphs of bounded degree (Beck)
 Size Ramsey number for complete balanced bipartite graphs (Faudree, Rousseau, Schelp)
 Size Ramsey number for unions of stars (Burr, Faudree, Rousseau, Schelp)
 A linear bound on some size Ramsey numbers (Faudree, Rousseau, Schelp)
 A linear bound on some size Ramsey numbers for particular graphs (Faudree, Rousseau, Schelp)
 A linear bound on some size Ramsey numbers for trees (Faudree, Rousseau, Schelp)
 A linear bound on some size Ramsey numbers for odd cycles (Faudree, Rousseau, Schelp)
 A linear bound on some size Ramsey numbers for cycles (Faudree, Rousseau, Schelp)
 Upper bound on induced Ramsey numbers (Rödl)
 Double exponential lower bound for \(3\)uniform hypergraph Ramsey numbers (Hajnal, Rado) ($500)
 Asymptotic behavior of \(t\)uniform hypergraph Ramsey numbers (Hajnal, Rado)
 Asymptotic behavior of generalized Ramsey numbers
 Behavior of generalized hypergraph Ramsey numbers ($500)
 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 nondegenerate 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/2n/2n/2) \) conjecture (Füredi, Loebl, Sós)
 Making a trianglefree 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)
 Edgepartitioning 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
 Growth of girth in graphs with fixed chromatic number
 Counting vertices of a graph with large girth and chromatic number
 Finding subgraphs with large girth and chromatic number (Hajnal)
 Ratio of chromatic number to clique number
 Decomposing graphs into subgraphs with higher total chromatic number (Lovász)
 Bipartite graphs with high listchromatic numbers
 If \(G\) is \((a, b)\)choosable, then \(G\) is \((am, bm)\)choosable for every positive integer \(m\) (Rubin, Taylor)
 Estimate the maximum number of edges for a \(k\)critical graph on n vertices
 Find the exact maximum number of edges for a \(k\)critical graph on n vertices
 Critical graphs with large minimum degree
 Vertex critical graphs with many extra edges
 Bounding the strong chromatic index (Nešetřil)
 Many disjoint monochromatic triangles (Faudree, Ordman) (two problems combined)
 Edgecoloring to avoid large monochromatic stars (Faudree, Rousseau, Schelp)
 AntiRamsey graphs (Burr, Graham, Sós)
 AntiRamsey problem for balanced colorings
 Bounding the acyclic chromatic number for graphs of bounded degree
 Any graph of large chromatic number has an odd cycle spanning a subgraph of large chromatic number (Hajnal)
 Any graph of large chromatic number has many edgedisjoint cycles on one subset of vertices (Hajnal)
 Covering by \(4\)cycles
 Maximum chromatic number of the complement graph of graphs with fixed \(h(G)\) (Faudree)
 Ratio of clique partition number to clique covering number (Faudree, Ordman)
 Difference of clique partition number to clique covering number
 Maximum product of clique partition numbers for complementary graphs
 The ascending subgraph decomposition problem (Alavi, Boals, Chartrand, Oellermann)
 At what density is the chromatic number of a random graph r?
 Find the range of expected chromatic numbers for a random graph
 Random graphs contain cubes (Bollobás)
 Large independent sets in all large subgraphs of a random graph (Bollobás)
 Covering a random graph with triangles (Spencer)
 Avoiding antimonotone graph properties in a random graph (Suen, Winkler)
 Number of induced \(G\)subgraphs in a given graph
 Adding an edge to an extremal \(4\)cyclefree graph gives two \(4\)cycles (Siminovits)
 Number of triangles in a multipartite graph with large minimum degree (Bollobás, Szemerédi)
 Number of graphs with a forbidden subgraph (Kleitman, Rothschild)
 Regular induced subgraphs (Fajtlowicz, Staton)
 Graphs with induced subgraphs of any number of edges (McKay) ($100)
 Count the ways to add a K_{4} (Tuza)
 Number of trianglefree graphs
 Number of pentagons in a triangle free graph
 A conjecture of \(3\)colored triangles in the complete graph (Sós)
 Turán's conjecture: hypergraph Turán numbers: \(t_r(n, k)\) (Turán, not Erdős) ($1000)
 Exact values for \(t_3(n, 4) \) (Turán, not Erdős) ($500)
 Asymptotics of \(t_3(n, 5)\) (Turán, not Erdős)
 Adding an edge to extremal \(K^{(3)}_k\)free graph gives two copies of \(K^{(3)}_k\)
 Adding an edge to extremal \(K^{(3)}_k\)free graph gives a \(K^{(3)}_{k+1}\) missing an edge
 Avoiding triple systems (Brown, Sós)
 Lower bound for hypergraph Turán numbers
 Turán densities are rational
 Unavoidable stars (Rado)
 Special case: unavoidable \(3\)stars
 Unavoidable stars of an nset (Szemerédi)
 Weak \(\Delta\)systems (Milner, Rado)
 Weak \(\Delta\)systems of an nset (Szemerédi)
 ErdősFaberLovász conjecture: a simple hypergraph on \(n\) vertices has chromatic index at most \(n\) (Faber, Lovász)
 Minimum number of edges for a \(n\)graph to not have Property B (that is: to not be \(2\)colorable)
 Minimum number of edges for a \(3\)chromatic \(4\)graph
 Conjecture on \(3\)chromatic hypergraphs (Lovász)
 Conjecture on minimum \(3\)chromatic hypergraphs (Lovász)
 Maximum edges in a \(3\)chromatic \(r\)clique (Lovász)
 Maximum vertices in a \(3\)chromatic \(r\)clique (Lovász)
 \(3\)chromatic cliques have edges with large intersection (Lovász) ($100)
 Number of sizes of edge intersections in a \(3\)chromatic \(r\)graph (Lovász)
 Jumping densities for \(3\)hypergraphs ($500)
 Conjecture on covering a hypergraph (Lovász)
 Stronger conjecture on covering a hypergraph
 Maximum unavoidable hypergraphs (Chung)
 Unavoidable stars with fixed intersection size (Duke)
 Hypergraph decomposition (Chung, Graham)
 Characterize hypergraphs with maximum/minimum product of point and line covering numbers (Chung, Graham)
 Covering complete \(3\)graphs (Tuza)
 \(r\)sets with common union and intersection (Füredi)
 Finding small global vertex covers for rgraphs with small local vertex covers (Fon der Flaass, Kostochka, Tuza)
 A Ramseytype conjecture for \(2\)colorings of complete \(3\)graphs
 A RamseyTurán upper bound for \(3\)graphs
 A RamseyTurán lower bound for \(3\)graphs (Sós)
 Menger's theorem for infinite graphs
 Ordinal Ramsey: For which \(\alpha\) does \(\omega^{\alpha} → (\omega^{\alpha}, 3)^{2}\)? (Hajnal) ($1000)
 Ordinal Ramsey: If \(\alpha → (\alpha, 3)^{2},\) then \(\alpha → (\alpha, 4)^{2}\) (Hajnal)
 Ordinal Ramsey: \(\omega_{1} → (\alpha, 4)^{3}\) for \(\alpha < \omega_{1}\)
 Ordinal Ramsey: \(\omega_{1}^{2} → (\omega_{1}^{2}, 3)^{2}\)
 Ordinal Ramsey: \(\omega_{3} → (\omega_{2} + 2)^{3}_{\omega}\)
 Almostbipartite graphs with infinite chromatic number (Hajnal, Szemerédi) ($250)
 Another problem on almostbipartite graphs with infinite chromatic number
 Uncountablechromatic graphs have common \(4\)chromatic subgraphs (Hajnal)
 Infinite \(K_{4}\)free graphs are the union of trianglefree countable graphs (Hajnal) ($250)
 The harmonic sums of oddcycle lengths diverges for graphs of infinite chromatic number (Hajnal)
 There is an uncountablechromatic graph \(G\) so that the size of the smallest \(n\)chromatic subgraph grows arbitrarily slowly (Hajnal, Szemerédi)
 Infinite graphs have infinite paths or arbitrary independent sets (Hajnal, Milner)
 Downup matchings in infinite graphs (Larson)
Extremal Graph Theory
Coloring, Packing, and Covering
Random Graphs and Graph Enumeration
Hypergraphs
Infinite Graphs