OP-9622Graph theoryStatus unassessed
On the clique number of the Paley Graph — Problem 29
On the clique number of the Paley Graph — Problem 29
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
The index
Explore the frontier
854 entries matching the current filters. Sorted by recently added.
OP-9621Graph theoryStatus unassessed
On the clique number of the Paley Graph — Problem 28
On the clique number of the Paley Graph — Problem 28
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9620Graph theoryStatus unassessed
On the clique number of the Paley Graph — Problem 27
On the clique number of the Paley Graph — Problem 27
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9619Graph theoryStatus unassessed
On the clique number of the Paley Graph — Problem 26
On the clique number of the Paley Graph — Problem 26
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9618Graph theoryStatus unassessed
On the clique number of the Paley Graph — Problem 25
On the clique number of the Paley Graph — Problem 25
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9612Graph theoryStatus unassessed
The Lovász number of random circulant graphs — Problem 18
The Lovász number of random circulant graphs — Problem 18
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9611Graph theoryStatus unassessed
The Lovász number of random circulant graphs — Problem 17
The Lovász number of random circulant graphs — Problem 17
Randomstrasse101 — Open Problems of 2025· Specialist source · status unassessed
OP-9393Graph theoryOpen
Erdős #1182 · graph theory / ramsey theory
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 $ leq F(…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9391Graph theoryOpen
Erdős #1178 · graph theory / hypergraphs
For r geq 3 let d r(e) be the minimal d such that mathrm ex r(n, mathcal F )=o(n^2), where mathcal F is the family of r -uniform hypergraphs on d vertices with e edges. Prove that d r(e)=(r-…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9376Graph theoryOpen
Erdős #1156 · graph theory / chromatic number
Let G be a random graph on n vertices, in which every edge is included independently with probability 1/2 . Is there some constant C such that that chromatic number chi(G) is, almost surely, concentrated on a…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9375Graph theoryOpen
Erdős #1155 · graph theory
Construct a random graph on n vertices in the following way: begin with the complete graph K n . At each stage, choose uniformly a random triangle in the graph and delete all the edges of this triangle. Repeat until t…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9355Graph theoryOpen
Erdős #1111 · graph theory
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 geq 1 then there exists d geq 1 such that if chi(G) geq d and $ o…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9349Graph theoryOpen
Erdős #1104 · graph theory / chromatic number
Let f(n) be the maximum possible chromatic number of a triangle-free graph on n vertices. Estimate f(n) .
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9329Graph theoryOpen
Erdős #1068 · graph theory / set theory
Does every graph with chromatic number aleph 1 contain a countable subgraph which is infinitely vertex-connected?
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9328Graph theoryOpen
Erdős #1066 · graph theory / planar graphs
Let G be a graph given by n points in mathbb R ^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 …
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9309Graph theoryOpen
Erdős #1035 · graph theory
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 ?
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9308Graph theoryOpen
Erdős #1033 · graph theory
Let h(n) be such that every graph on n vertices with n^2/4 many edges contains a triangle whose vertices have degrees summing to at least h(n) . Estimate h(n) . In particular, is it true that h(n) geq (2( sq…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9307Graph theoryOpen
Erdős #1032 · graph theory / chromatic number
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 verti…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9306Graph theoryOpen
Erdős #1030 · graph theory / ramsey theory
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 …
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9305Graph theoryOpen
Erdős #1029 · graph theory / ramsey theory
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 frac R(k) k2^ k/2 to infty.
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9304Graph theoryOpen
Erdős #1020 · graph theory / hypergraphs
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 geq 3 , f(n;r,k)= max left( binom rk-1 r , binom n r - binom n-k+1 r r…
Erdős Problems (Thomas Bloom)· Source reports FALSIFIABLE
OP-9303Graph theoryOpen
Erdős #1017 · graph theory
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 .
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9302Graph theoryOpen
Erdős #1016 · graph theory / cycles
Let h(n) be minimal such that there is a graph on n vertices with n+h(n) edges which contains a cycle on k vertices, for all 3 leq k leq n . Estimate h(n) . In particular, is it true that h(n) geq log 2n+…
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9301Graph theoryOpen
Erdős #1013 · graph theory / chromatic number
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 to infty frac h 3(k+1) h 3(k) =1.
Erdős Problems (Thomas Bloom)· Source reports OPEN
OP-9300Graph theoryOpen
Erdős #1011 · graph theory
Let f r(n) be minimal such that every graph on n vertices with geq f r(n) edges and chromatic number geq r contains a triangle. Determine f r(n) .
Erdős Problems (Thomas Bloom)· Source reports OPEN
Frequent tags
theoremdb 3909historical workshop 3469aim 3469icm 2898source curated 2675source candidate 1231number theory 1007status unassessed 622specialist collection 522pde dyn 399geometry 336analysis 269algebraic geometry 257algebra 224verifiable 2026 223probability 221graph theory 200topology 199lie rep 180combinatorics 154combinatorics discrete mathematics 141mathematical physics mechanics 137numerical analysis computer science 131research 2026 126