Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether the largest girth of a graph on n vertices with chromatic number k, divided by the logarithm of n, tends to a limit, for k at least four.
Asks whether the largest ratio of chromatic to clique number on n vertices, divided by n over the squared logarithm of n, tends to a limit.
Asks whether a graph of chromatic number k with no k-vertex clique has disjoint subgraphs of chromatic number at least a and at least b when a plus b is k+1.
Asks for the least number of vertices n(k) of a bipartite graph whose list chromatic number exceeds k; open, with n(2) = 6 and n(3) = 14 known.
Bounds the list chromatic number, the least list size per vertex always permitting a proper coloring from the lists, for graphs of a given kind.
Asks whether every planar graph has list chromatic number at most 5, the least list size per vertex always allowing a proper coloring from the lists, and whether 5 is best possible.
Asks whether choosability from lists of a colors with b chosen per vertex implies the same for other pairs of list size and choice size.
Characterizes the triangles that can only be cut into a square number of congruent triangles.
Determines all n for which some triangle can be cut into n congruent triangles.
Asks how large a subset of the first N integers can be if no difference of at least t between two of its elements divides the larger element.
Asks whether a graph on n vertices with no large clique or independent set has many induced subgraphs that pairwise differ in vertex count or edge count.
Asks whether a graph on n vertices with no large clique or independent set has an induced subgraph on many vertices realizing many distinct degrees.
Asks whether a hereditary family of finite graphs forcing monochromatic triangles under every finite number of colors holds the finite subgraphs of a graph forcing them under any infinite cardinal; a disproof is claimed.
Asks whether any two-coloring of the edges of K_n leaves at most n²/4 edges on no monochromatic triangle for large n, as Erdős stated it; proved by Keevash and Sudakov's exact theorem, while the site's wording fails for n from 3 to 6.
Asks whether large enough chromatic number forces an odd cycle whose vertices span a subgraph of chromatic number at least k, for k at least three.
Asks whether a high enough chromatic number forces a graph to contain k edge-disjoint cycles on the same vertex set, for every k.
Asks whether a graph on n vertices in which every cycle has more vertices than chords can have at most a constant times n edges.
Estimates how many edges force a t-uniform hypergraph on n vertices to have four edges with A union B equal to C union D and A, B and C, D disjoint.
Bounds the size of a set meeting all k-element sets of a family in which every r of them share a piercing pair, asking if it is a constant times k.
Asks whether every two-coloring of the positive integers has a monochromatic three-term progression whose difference exceeds its first term; proved by Brown and Landman in 1999, with an elementary argument recorded by the site.
Asks whether, for any finitely many distinct primes, infinitely many n make n factorial divisible by an even power of each of those primes.
Asks whether some n greater than 24 has m plus the number of divisors of m at most n plus two for every m less than n.
Estimates the length of the longest chain of integers below n whose greatest prime factors are strictly decreasing.
Asks whether for any two primes p and q there is an integer n whose greatest prime factor is p while that of n plus one is q.
Asks for the least number of distinct multiples of distinct members of an m-set in the first N integers that every interval of length 2N holds; it is min(m, ceiling of 2 root m), by van Doorn, Li and Tang (2026); not root m.