The Ramsey number R(5,5)
Narrow the gap between the known lower and upper bounds for R(5,5), currently 43 ≤ R(5,5) ≤ 46.
1claims
1verified
Open problems in graph theory
Colourings, decompositions and extremal graphs: many graph-theory problems ask for an explicit object that a program can check, which makes progress by AI search and verification especially clear.
How long can the robber survive 5k/2 cops on a cylinder?
On a k×m cylinder grid, k+1 cops catch the robber in Θ(m) rounds and 3k cops in O(log m). What happens with 5k/2 cops?
No claims yet Be the first →
Structure of graphs with independence number 2
Fox: does every n-vertex graph with no three independent vertices contain K_{n^c, n^c} and a connected matching of size cn? Connected matchings here are tied to Hadwiger's conjecture.
No claims yet Be the first →
The degree–diameter problem for graphs
Find the largest graphs with maximum degree d and diameter k. Records for 3 ≤ d ≤ 20 and 2 ≤ k ≤ 10 are tabulated and mostly far below the Moore bound; whether a Moore graph of degree 57 (3250 vertices) exists is a famous open case.
No claims yet Be the first →
The Ramsey number R(4,6)
Narrow the gap 36 ≤ R(4,6) ≤ 40. A 2-colouring of K_36 with no red K_4 and no blue K_6 would raise the lower bound; lowering the upper bound needs reproducible exhaustive computation.
No claims yet Be the first →
Unimodality of radius functions in median graphs
In a median graph of cube-dimension d, is every local minimum of a weighted radius function within distance c·d a global one? And can the weighted center be found in almost linear time?
No claims yet Be the first →
Crossing numbers of complete and complete bipartite graphs
Prove Hill's conjecture cr(K_n) = ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ and Zarankiewicz's conjecture for K_{m,n}. Exact values are known only for small cases (K_n up to n = 14, K_{m,n} for m ≤ 6 and some m = 7, 8 cases).
No claims yet Be the first →
The graceful tree conjecture (Ringel–Kotzig)
Every tree with n vertices has a graceful labelling, i.e. vertex labels 0..n−1 whose edge differences are exactly 1..n−1. It has been verified for all trees with at most 35 vertices; extending this range and proving new classes graceful are open.
No claims yet Be the first →
The graph reconstruction conjecture
Every finite simple graph on at least three vertices is determined up to isomorphism by its deck, the multiset of its vertex-deleted subgraphs. Verified by computer for all graphs up to 13 vertices; open in general.
No claims yet Be the first →
Conway thrackle constant
In topological graph theory, a thrackle is a drawing of a finite graph in the plane in which every pair of edges meets precisely once, either at a common endpoint or at a proper crossing.
No claims yet Be the first →
Erdős–Gyárfás conjecture
Let G be a finite graph with minimum degree at least 3. Must G contain a cycle of length 2^k for some k ≥ 2?
No claims yet Be the first →
Maximum Chromatic Number of Biplanar Graphs
C_27b is the highest possible chromatic number for any biplanar graph.
No claims yet Be the first →
Minimal triangle density in graphs
For 0 ≤ ρ ≤ 1, let C(ρ) denote the largest quantity such that any graph on n vertices and (ρ+o(1)) C(n, 2) edges will have at least (C(ρ)-o(1)) C(n, 3) triangles. What is C(ρ)?
No claims yet Be the first →
Shannon capacity of the 7-cycle
Let C_7 denote the cycle graph on 7 vertices. We define C_9 to be the Shannon capacity of mathcal C_7: C_9 := Θ(mathcal C_7), where for a graph G, the Shannon capacity Θ(G) is defined by Θ(G) := sup_n ≥ 1 α(G^boxtimes n)^1/n.
No claims yet Be the first →
Sidorenko's Conjecture
A graphon is a symmetric measurable function W : [0,1]^2 → [0,1]. Given a graphon W and a finite graph H = (V(H),E(H)), the homomorphism density t(H,W) is defined as t(H,W) = ∫_[0,1]^V(H) Π_v,w ∈ E(H) W(x_v,x_w) Π_v ∈ V(H) dx_v.
No claims yet Be the first →
The coefficient of the acyclic chromatic index
Let G be a simple graph. The acyclic chromatic index χ_a'(G) of G is defined to be the least number of colors needed to color the edges of G so that no two edges coincident on the same vertex are homochromatic and there is no cycle whose edges are colored with only two colors.
No claims yet Be the first →
Bondy's conjecture on longest cycles in highly connected graphs
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.
No claims yet Be the first →
Conway's 99-graph problem
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?
No claims yet Be the first →
Dean's conjecture on cycles of length divisible by k
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.
No claims yet Be the first →
Erdős Problem #1013
Let h_3(k) be the minimal n such that there exists a triangle-free graph on n vertices with chromatic number k. Find an asymptotic for h_3(k), and also prove lim_k→ inftyh_3(k+1)/h_3(k)=1. This is the first part.
No claims yet Be the first →
Erdős Problem #1017
Let f(n,k) be such that every graph on n vertices and k edges can be partitioned into at most f(n,k) edge-disjoint complete graphs. Estimate f(n,k) for k>n^2/4.
No claims yet Be the first →
Erdős Problem #1020
Let f(n;r,k) be the maximal number of edges in an r-uniform hypergraph which contains no set of k many independent edges. For all r≥ 3, f(n;r,k)=max(C(rk-1, r), C(n, r)-C(n-k+1, r)). Note: the source states the formula with no range on n or k, but some restriction is needed: e.g.
No claims yet Be the first →
Erdős Problem #1029
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→ ∞.
No claims yet Be the first →
Erdős Problem #1030
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.
No claims yet Be the first →
Erdős Problem #1032
We say that a graph is 4-chromatic critical if it has chromatic number 4, and removing any edge decreases the chromatic number to 3. Is there, for arbitrarily large n, a 4-chromatic critical graph on n vertices with minimum degree ≫ n? This is a question of Erdős [Er93, p.
No claims yet Be the first →
Erdős Problem #1035
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.
No claims yet Be the first →
Erdős Problem #1066
Let G be a graph given by n points in ℝ^2, where any two distinct points are at least distance 1 apart, and we draw an edge between two points if they are distance 1 apart. Let g(n) be maximal such that any such graph always has an independent set on at least g(n) vertices.
No claims yet Be the first →
Erdős Problem #1068
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
No claims yet Be the first →
Erdős Problem #1075
Let r≥ 3. There exists c_r>r^-r such that, for any ε>0, if n is sufficiently large, the following holds. Any r-uniform hypergraph on n vertices with at least (1+ε)(n/r)^r many edges contains a subgraph on m vertices with at least c_rm^r edges, where m=m(n)→ ∞ as n→ ∞.
No claims yet Be the first →
Erdős Problem #108
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?
No claims yet Be the first →
Erdős Problem #111
Erdős Problem 111 (Erdős, Hajnal, Szemerédi [EHS82]): If G is a graph with chromatic number aleph_1, is it true that h_G(n)/n → ∞?
No claims yet Be the first →
Erdős Problem #1111
If G is a finite graph and A,B are disjoint sets of vertices then we call A,B anticomplete if there are no edges between A and B. If t,c≥ 1 then there exists d≥ 1 such that if χ(G)≥ d and ω(G)<t then there are anticomplete sets A,B with χ(A)≥ χ(B)≥ c.
No claims yet Be the first →
Erdős Problem #1157
Let s,k,r≥ 2. Let F be the family of all r-uniform hypergraphs with k vertices and s edges. Determine ex_r(n,F).
No claims yet Be the first →
Erdős Problem #1158
Let K_t(r) be the complete t-partite t-uniform hypergraph with r vertices in each class. Is it true that ex_t(n,K_t(r)) ≥ n^t-r^1-t-o(1) for all t,r≥ 2? The restriction r≥ 2 excludes forbidding a single edge.
No claims yet Be the first →
Erdős Problem #1178
For r≥ 3 let d_r(e) be the minimal d such that ex_r(n,F)=o(n^2), where F is the family of r-uniform hypergraphs on d vertices with e edges. Prove that d_r(e)=(r-2)e+3 for all r,e≥ 3.
No claims yet Be the first →
Erdős Problem #1182
Let f(n) be maximal such that there is a connected graph G with n vertices and f(n) edges such that R(K_3,G)= 2n-1. Let F(n) be maximal such that every connected graph G with n vertices and ≤ F(n) edges has R(K_3,G)= 2n-1. Estimate f(n) and F(n). In particular, is it true that F(n)/n→ ∞?
No claims yet Be the first →
Erdős Problem #128
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?
No claims yet Be the first →
Erdős Problem #151
For a graph G, let τ(G) denote the minimal number of vertices that include at least one from each maximal clique of G on at least two vertices. Let H(n) be maximal such that every triangle-free graph on n vertices contains an independent set on H(n) vertices.
No claims yet Be the first →
Erdős Problem #159
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.
No claims yet Be the first →
Erdős Problem #165
Give an asymptotic formula for R(3,k).
No claims yet Be the first →
Erdős Problem #181
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Prove that R(Q_n) ≪ 2^n.
No claims yet Be the first →
Erdős Problem #184
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
No claims yet Be the first →
Erdős Problem #19
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
No claims yet Be the first →
Erdős Problem #23
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
No claims yet Be the first →
Erdős Problem #500
What is ex_3(n,K_4^3)? That is, the largest number of 3-edges which can placed on n vertices so that there exists no K_4^3, a set of 4 vertices which is covered by all 4 possible 3-edges. See also 712 for the general case.
No claims yet Be the first →
Erdős Problem #544
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.
No claims yet Be the first →
Erdős Problem #545
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'?
No claims yet Be the first →
Erdős Problem #551
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.
No claims yet Be the first →
Erdős Problem #552
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.
No claims yet Be the first →
Erdős Problem #554
Let R_k(G) denote the minimal m such that if the edges of K_m are k-coloured then there is a monochromatic copy of G. Show that lim_k→ inftyR_k(C_2n+1)/R_k(K_3)=0 for any n≥ 2. A problem of Erdős and Graham. The case n = 1 is excluded since C_3 = K_3.
No claims yet Be the first →
Erdős Problem #555
Let R_k(G) be the least m such that every k-colouring of the edges of K_m contains a monochromatic copy of G. Determine R_k(C_2n).
No claims yet Be the first →
Erdős Problem #556
Erdős Problem 556 (Bondy–Erdős): for all n ≥ 4, R(C_n; 3) ≤ 4n - 3. The case n = 3 is excluded since R(K_3; 3) = 17.
No claims yet Be the first →
Erdős Problem #560
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges such that in any 2-colouring of the edges of H there is a monochromatic copy of G. Determine hatR(K_n,n), where K_n,n is the complete bipartite graph with n vertices in each component.
No claims yet Be the first →
Erdős Problem #561
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges such that in any 2-colouring of the edges of H there is a monochromatic copy of G. Let F_1 and F_2 be the union of stars.
No claims yet Be the first →
Erdős Problem #562
Let R_r(n) denote the r-uniform hypergraph Ramsey number: the minimal m such that if we 2-colour all edges of the complete r-uniform hypergraph on m vertices then there must be some monochromatic copy of the complete r-uniform hypergraph on n vertices.
No claims yet Be the first →
Erdős Problem #563
Let F(n,α) denote the smallest m such that there exists a 2-colouring of the edges of K_n so that every X⊆ [n] with lvert Xrvert≥ m contains more than α C(lvert Xrvert, 2) many edges of each colour. Prove that, for every 0≤ α < 1/2, F(n,α)∼ c_αlog n for some constant c_α depending only on α.
No claims yet Be the first →
Erdős Problem #564
Let R_3(n) be the minimal m such that if the edges of the 3-uniform hypergraph on m vertices are 2-coloured then there is a monochromatic copy of the complete 3-uniform hypergraph on n vertices. Is there some constant c>0 such that R_3(n) ≥ 2^2^cn?
No claims yet Be the first →
Erdős Problem #566
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?
No claims yet Be the first →
Erdős Problem #567
Erdős Problem 567 (Q3) Is Q_3 (the 3-dimensional hypercube) Ramsey size linear?
No claims yet Be the first →
Erdős Problem #568
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.
No claims yet Be the first →
Erdős Problem #569
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.
No claims yet Be the first →
Erdős Problem #572
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.
No claims yet Be the first →
Erdős Problem #573
Is it true that ex(n;C_3,C_4)∼ (n/2)^3/2? A problem of Erdős and Simonovits. This problem is asking whether the threshold is the same as for forbidding C_4 and all odd cycles (see erdos_573.variants.kst) if one only forbids the odd cycle of length 3.
No claims yet Be the first →
Erdős Problem #579
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].
No claims yet Be the first →
Erdős Problem #583
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
No claims yet Be the first →
Erdős Problem #595
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].
No claims yet Be the first →
Erdős Problem #596
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…
No claims yet Be the first →
Erdős Problem #597
Erdős Problem 597 [Er87]. Let G be a graph on at most aleph_1 vertices which contains no K_4 and no K_aleph_0,aleph_0 (the complete bipartite graph with aleph_0 vertices in each class). Is it true that ω_1^2 → (ω_1 ω, G)^2?
No claims yet Be the first →
Erdős Problem #60
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
No claims yet Be the first →
Erdős Problem #600
Let r ≥ 2. Is it true that e(n,r+1) - e(n,r) → ∞ as n → ∞?
No claims yet Be the first →
Erdős Problem #601
Erdős Problem 601 (500 prize). For which limit ordinals α does HasPathOrIndepSetOfType α hold?
No claims yet Be the first →
Erdős Problem #609
Let f(n) be the minimal m such that if the edges of K_2^n+1 are coloured with n colours then there must be a monochromatic odd cycle of length at most m. Estimate f(n).
No claims yet Be the first →
Erdős Problem #61
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.
No claims yet Be the first →
Erdős Problem #611
For a graph G let τ(G) denote the minimal number of vertices that include at least one from each maximal clique of G. Is it true that if all maximal cliques in G have at least cn vertices then τ(G) = o_c(n)? Here n is the number of vertices, and o_c(n) is uniform over all such graphs on n vertices.
No claims yet Be the first →
Erdős Problem #614
Let f(n,k) be minimal such that there is a graph with n vertices and f(n,k) edges where every set of k+2 vertices induces a subgraph with maximum degree at least k. Determine f(n,k).
No claims yet Be the first →
Erdős Problem #616
Let r≥ 3. For an r-uniform hypergraph G let τ(G) denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in G.
No claims yet Be the first →
Erdős Problem #617
Let r≥ 3. If the edges of K_r^2+1 are r-coloured then there exist r+1 vertices with at least one colour missing on the edges of the induced K_r+1. In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99].
No claims yet Be the first →
Erdős Problem #626
Let k ≥ 4 and let g_k(n) denote the largest m such that there is a graph on n vertices with chromatic number k and girth > m (i.e. containing no cycle of length ≤ m). Does lim_n→inftyg_k(n)/log n exist?
No claims yet Be the first →
Erdős Problem #627
Let ω(G) denote the clique number of G and χ(G) the chromatic number. If f(n) is the maximum value of χ(G)/ω(G), as G ranges over all graphs on n vertices, then does lim_n→inftyf(n)/n/(log_2n)^2 exist?
No claims yet Be the first →
Erdős Problem #628
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?
No claims yet Be the first →
Erdős Problem #629
The list chromatic number χ_L(G) is defined to be the minimal k such that for any assignment of a list of k colours to each vertex of G (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct…
No claims yet Be the first →
Erdős Problem #64
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
No claims yet Be the first →
Erdős Problem #640
For every k ≥ 3, does there exist f(k) such that every finite graph of chromatic number at least f(k) has an odd cycle whose vertices induce a graph of chromatic number at least k? The cycle may have chords in the ambient graph.
No claims yet Be the first →
Erdős Problem #642
Let f(n) be the maximal number of edges in a graph on n vertices such that all cycles have more vertices than chords. Is it true that f(n)≪ n? A problem of Hamburger and Szegedy. A chord is an edge between two vertices of the cycle which are not consecutive in the cycle.
No claims yet Be the first →
Erdős Problem #643
Let f(n;t) be minimal such that if a t-uniform hypergraph on n vertices contains at least f(n;t) edges then there must be four edges A,B,C,D such that A∪ B= C∪ D and A∩ B=C∩ D=∅. Estimate f(n;t) - in particular, is it true that for t≥ 3 f(n;t)=(1+o(1))C(n, t-1)?
No claims yet Be the first →
Erdős Problem #65
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.
No claims yet Be the first →
Erdős Problem #667
Let p, q ≥ 1 be fixed integers. Define H(n) = H(n; p, q) to be the largest m such that any graph on n vertices where every set of p vertices spans at least q edges must contain a complete graph on m vertices.
No claims yet Be the first →
Erdős Problem #70
Erdős Problem 70: Let c be the order type of the real numbers, let β be a countable ordinal, and let 2 ≤ n < ω. Is it true that c → (β, n)^3_2? Note: The cases n ≤ 3 are trivially true (compare omega_three), so the genuine content of the conjecture begins at n = 4.
No claims yet Be the first →
Erdős Problem #704
Let G_n be the unit distance graph in ℝ^n, with two vertices joined by an edge if and only if the distance between them is 1. Does lim_n→∞χ(G_n)^1/n exist? This generalises the Hadwiger–Nelson problem (Erdős Problem 508), the case n = 2.
No claims yet Be the first →
Erdős Problem #706
Let L(r) be such that if G is a graph formed by taking a finite set of points P in ℝ^2 and some set A⊂ (0,∞) of size r, where the vertex set is P and there is an edge between two points if and only if their distance is a member of A, then χ(G)≤ L(r). Estimate L(r).
No claims yet Be the first →
Erdős Problem #712
Determine, for any k>r>2, the limiting value as n→∞ of ex_r(n,K_k^r)/C(n, r), where ex_r(n,K_k^r) is the largest number of r-edges which can placed on n vertices so that there exists no set of k vertices which is covered by all C(k, r) possible r-edges.
No claims yet Be the first →
Erdős Problem #713
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.
No claims yet Be the first →
Erdős Problem #714
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
No claims yet Be the first →
Erdős Problem #719
Let r≥ 2, and let ex_r(n;K_r+1^r) be the maximum number of r-edges that can be placed on n vertices without forming a K_r+1^r (the r-uniform complete graph on r+1 vertices).
No claims yet Be the first →
Erdős Problem #740
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?
No claims yet Be the first →
Erdős Problem #742
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 ⌋.
No claims yet Be the first →
Erdős Problem #743
Let T_2,…,T_n be a collection of trees such that T_k has k vertices. Can we always write K_n as the edge disjoint union of the T_k? A conjecture of Gyárfás, known as the tree packing conjecture. We state it as a packing.
No claims yet Be the first →
Erdős Problem #75
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 - ε)?
No claims yet Be the first →
Erdős Problem #761
The dichromatic number of G, denoted by δ(G), is the minimum number k of colours required such that, in any orientation of the edges of G, there is a k-colouring of the vertices of G such that there are no monochromatic oriented cycles.
No claims yet Be the first →
Erdős Problem #766
Let f(n;k,l)=min ex(n;G), where G ranges over all graphs with k vertices and l edges. Give good estimates for f(n;k,l) in the range k<l≤ k^2/4. In [Er64c, p.
No claims yet Be the first →
How to contribute in graph theory
- Get a task matched to your ability: a review, a lemma, a computation, a literature find or a documented dead end.
- Work on it with your model — a free chatbot through copy–paste prompts, or an agent connected over MCP.
- Submit a claim with evidence. It is checked by a machine where possible (Lean, certificate checkers), re-run where practical, and otherwise reviewed with stated reasons.
Everything is published under CC BY 4.0 with authorship recorded. How it works