Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
606 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Determines the largest number of edges of a bipartite subgraph that every triangle-free graph with m edges must contain; known to the order m/2 + Theta(m^{4/5}) by Alon, the exponent sharp and the exact value open.
Asks whether there is a graph with no complete subgraph on four vertices in which every two-coloring of the edges produces a monochromatic triangle.
Asks whether there is a system of congruences covering all integers in which no modulus divides another.
Determines the largest set of integers up to N in which no non-empty subset has a square sum.
Asks whether every red-blue coloring of the pairs from the ordinal omega to the omega yields a red complete subgraph of that order type or a blue triangle.
Asks whether every red-blue coloring of pairs from the ordinal omega to the omega squared gives a red complete subgraph of that order type or a blue triangle.
Asks whether every graph with chromatic number at least the first uncountable cardinal contains all sufficiently large odd cycles.
Asks whether every graph with two disjoint independent sets has a family of disjoint paths between them plus a blocking set meeting each path once.
The least number of colors always enough to color the union of countably infinite sets meeting pairwise in a set of size other than two with none one color.
Asks whether n points can be placed on a sphere so that the number of pairs at one repeated distance exceeds any fixed multiple of n as n grows.
Asks which values can occur as the number of distinct lines determined by n distinct points in the plane; determined for all sufficiently large n; the small cases are open.
Asks whether the number of distinct sets of line sizes determined by n points in the plane is at most exp(O(sqrt n)).
Asks whether every graph on n vertices with more than a quarter of n squared edges has at least two ninths of n squared edges lying on five-cycles.
Bounds the clique transversal number of an n-vertex graph; proved, with the answer n − Θ(√(n log n)), by the Joret–Micek–Reed–Smid clique-coloring bound and Kim's triangle-free graphs, under the site's PROVED (LEAN) label.
Asks whether every graph with one edge fewer than a conjectured size Ramsey number splits into a bipartite graph and a graph of maximum degree below n; disproved for every n at least five by Pikhurko's constructions.
Asks whether a fixed saving below an eighth of n squared edges forces a graph on n vertices to contain a four-vertex clique or an independent set of n over log n vertices; disproved by Fox, Loh and Zhao.
Records Alon's subquadratic triangle-free diameter-two completion theorem, the catalog's notation and diameter qualifications, and the earlier bounded-degree results.
Asks whether every connected triangle-free graph can be augmented to diameter at most four, still triangle-free, using fewer than (1-c)n edges.
Compares the largest set of edges meeting each triangle at most once with the fewest edges meeting every triangle, in a graph on n vertices.
Every regular graph of degree n plus one on two n vertices has a positive proportion of cyclic vertex subsets; the limiting constant is one half.
Compares the cochromatic number, the fewest colors whose classes each induce a complete or empty graph, with the ordinary chromatic number.
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.