Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
58 shown· page 1 of 2
Conjecture 1 (Bondy, 1980). Let k ≥ 1 and let G be a k-connected graph on n vertices. If δ(G) ≥ n + k(k-1)/k+1, then for every longest cycle C of G, every path in G - V(C) has at most k-1 vertices.
Does there exist an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors?
Conjecture 1.1 (Dean, 1988). For every integer k ≥ 3, every finite simple graph with minimum degree at least k contains a cycle whose length is divisible by k. A cycle has length at least 3, so the divisor is never 0 and the statement is not satisfied for a trivial reason.
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then R(k)/k2^k/2→ ∞.
Let R(k,l) be the usual Ramsey number: the smallest n such that if the edges of K_n are coloured red and blue then there exists either a red K_k or a blue K_l. Prove the existence of some c>0 such that lim_k→ inftyR(k+1,k)/R(k,k)> 1+c. A problem of Erdős and Sós.
Is there a constant c > 0 such that every graph on 2^n vertices with minimum degree > (1-c) · 2^n contains the n-dimensional hypercube Q_n? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal number of edges that guarantee a Q_n.
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
Let G be a graph with n vertices such that every induced subgraph on ≥ n/2 vertices has more than n^2/50 edges. Must G contain a triangle?
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c. The prize of 100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let m be sufficiently large and let G be a graph with m edges and no isolated vertices. Is the Ramsey number R(G) maximised when G is 'as complete as possible'?
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
Determine the Ramsey number R(C_4, S_n), where S_n=K_1,n is the star on n+1 vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Let δ > 0. If n is sufficiently large and G is a graph on n vertices with no K_2,2,2 (the octahedron) and at least δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
Erdős Problem 595 (\250): Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
The Erdős–Hajnal Conjecture states that there is a constant c(H) > 0 for each H such that we can take f(n) = n^c(H) in the above formulation.
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)∼ cn^α? The condition that G have at least two edges excludes degenerate forbidden graphs whose extremal number is eventually zero, for which the displayed asymptotic with c>0 is impossible.
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
Murty-Simon Conjecture Let G be a graph on n vertices with diameter 2 such that deleting any edge increases the diameter. Is it true that G has at most ⌊ n^2 / 4 ⌋ edges? Equality is conjectured to hold for the complete balanced bipartite graph K_⌈ n/2 ⌉, ⌊ n/2 ⌋.
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then find the value of lim_k→ inftyR(k)^1/k. This problem is #3 in Ramsey Theory in the graphs problem collection.
Let R(k) be the Ramsey number for K_k. Give a constructive proof that R(k) > C^k for some constant C > 1. Equivalently, give an explicit construction of graphs on n vertices which contain no clique and no independent set of size ≥ c log n, for some constant c > 0.
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Is it true that every subgraph of Q_n with ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.
For A⊆ 1,…,n let G(A) be the graph with vertex set A, where two integers are joined by an edge if they are coprime. Is it true that if |A| > ⌊ n/2 ⌋ + ⌊ n/3 ⌋ - ⌊ n/6 ⌋ then G(A) contains all odd cycles of length ≤ n/3 + 1? A problem of Erdős and Sárközy [ErSa97].
Erdős Problem #918
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T via cyclic shifts of a single embedding.
The Latin Tableau Conjecture: If G is the simple graph of a Young diagram, then G is CDS-colorable.
The pebbling number conjecture: the pebbling number of a Cartesian product of connected graphs is at most equal to the product of the pebbling numbers of the factors. See Asplund, Hurlbert, and Kenter.
For a graph G, we define Δ(G) to be the maximum degree, ω(G) to be the size of the largest clique subgraph, and χ(G) to be the chromatic number. Reed's omega, delta, and chi conjecture states that χ(G) ≤ ⌈ 1/2(ω(G) + Δ(G) + 1) ⌉.
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T. A "copy" of T is the image T.map(f_i) of T under a vertex embedding f_i : V hookrightarrow Fin(2n+1); the copies are pairwise edge-disjoint and together cover every edge of K_2n+1.
Sidorenko's conjecture (1993). For every finite bipartite simple graph H and every finite simple graph G: t(H, G) ≥ t(K_2, G)^e(H), where K_2 denotes the single-edge graph on 2 vertices (i.e. completeGraph (Fin 2)).
Conjecture 4 (Alon-Tarsi, 1985). Every bridgeless graph has a list of cycles covering every edge, with Σ_C |E(C)| ≤ 7/5|E(G)|.
Sheehan's conjecture (1977). Every 4-regular graph with a Hamiltonian cycle has a second Hamiltonian cycle (one with a different edge set).
