Skip to content

Erdős Problems

1,217 source-owned questions · 604 with a formal statement · searchable by statement, number, topic and source status.

Add a contributionCollection details
Full distribution

Collection coverage

Source status, exact formal material, and reviewed Results are separate signals.

  • Open per source608
  • Resolved per source556
  • Other source status53
Exact formal statement available604 / 1,217
With Repository-reviewed evidence2 / 1,217
More filters

Coverage is source-observation coverage, not Problem completeness. Inspect coverage

Problems

61 Problems

1/2

SelectNumberQuestionOpen
#19No statement retained — open to read what the source holdsSource says decidableNo formal declaration
#57No statement retained — open to read what the source holdsSource says provedNo formal declaration
#58No statement retained — open to read what the source holdsSource says provedNo formal declaration
#63No statement retained — open to read what the source holdsSource says provedNo formal declaration
#74Let f(n)→∞f(n)\to \infty possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on nn vertices can be made bipartite by deleting at most f(n)f(n) edges?Source says openFormalized
#75Is 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 - ε)?Source says openFormalized
#108For 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?Source says openFormalized
#110No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#111No statement retained — open to read what the source holdsSource says openNo formal declaration
#130Let A⊂R2A\subset\mathbb{R}^2 be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in AA, where two vertices are joined by an edge if and only if they are an integer distance apart. How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?Source says openFormalized
#593Erdős Problem 593 (500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number >ℵ0> \aleph_0.Source says openFormalized
#625No statement retained — open to read what the source holdsSource says openNo formal declaration
#626No statement retained — open to read what the source holdsSource says openNo formal declaration
#627No statement retained — open to read what the source holdsSource says openNo formal declaration
#628Let GG be a graph with chromatic number kk containing no KkK_k. If a,b≥2a,b\geq 2 and a+b=k+1a+b=k+1 then must there exist two disjoint subgraphs of GG with chromatic numbers ≥a\geq a and ≥b\geq b respectively?Source says falsifiableFormalized
#629No statement retained — open to read what the source holdsSource says openNo formal declaration
#630No statement retained — open to read what the source holdsSource says provedNo formal declaration
#631No statement retained — open to read what the source holdsSource says provedNo formal declaration
#632No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#640No statement retained — open to read what the source holdsSource says openNo formal declaration
#704No statement retained — open to read what the source holdsSource says openNo formal declaration
#705Let GG be a finite unit distance graph in Unparsed notation: \mamthbb{R}^2. Is there some kk such that if GG has girth ≥k≥ k, then χ(G)≤3\chi(G) ≤ 3?Source says disprovedFormalized
#706No statement retained — open to read what the source holdsSource says openNo formal declaration
#736No statement retained — open to read what the source holdsSource says not provableNo formal declaration
#737No statement retained — open to read what the source holdsSource says provedNo formal declaration
#738No statement retained — open to read what the source holdsSource says openNo formal declaration
#739No statement retained — open to read what the source holdsSource says not provableNo formal declaration
#740Let m\mathfrak{m} be an infinite cardinal and GG be a graph with chromatic number m\mathfrak{m}. Let r≥1r\geq 1. Must GG contain a subgraph of chromatic number m\mathfrak{m} which does not contain any odd cycle of length ≤r\leq r?Source says openFormalized
#744No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#750Let f(m)f(m) be some function such that f(m)→∞f(m)\to \infty as m→∞m\to \infty. Does there exist a graph GG of infinite chromatic number such that every subgraph on mm vertices contains an independent set of size at least m2−f(m)\frac{m}{2}-f(m)?Source says proved (Lean)Formalized
#751Let GG be a graph with chromatic number χ(G)=4\chi(G)=4. If m1<m2<⋯m_1<m_2<\cdots are the lengths of the cycles in GG then can min⁡(mi+1−mi)\min(m_{i+1}-m_i) be arbitrarily large?Source says disproved (Lean)Formalized
#753The list chromatic number χL(G)\chi_L(G) is defined to be the minimal kk such that for any assignment of a list of kk colours to each vertex of GG (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 colours.Source says disproved (Lean)Formalized
#758No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#759No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#760The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG such that each colour class induces either a complete graph or independent set.Source says proved (Lean)Formalized
#761No statement retained — open to read what the source holdsSource says openNo formal declaration
#762The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG such that each colour class induces either a complete graph or empty graph.Source says disproved (Lean)Formalized
#780No statement retained — open to read what the source holdsSource says provedNo formal declaration
#797No statement retained — open to read what the source holdsSource says provedNo formal declaration
#799No statement retained — open to read what the source holdsSource says provedNo formal declaration
#832No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#833No statement retained — open to read what the source holdsSource says provedNo formal declaration
#836No statement retained — open to read what the source holdsSource says openNo formal declaration
#842No statement retained — open to read what the source holdsSource says provedNo formal declaration
#917No statement retained — open to read what the source holdsSource says openNo formal declaration
#918Is there a graph with ℵ2\aleph_2 vertices and chromatic number ℵ2\aleph_2 such that every subgraph on ℵ1\aleph_1 vertices has chromatic number ≤ℵ0\leq\aleph_0?Source says openFormalized
#919No statement retained — open to read what the source holdsSource says openNo formal declaration
#920Is it true that, for k≥4k\geq 4, fk(n)≫n1−1k−1(log⁡n)ckf_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}} for some constant ck>0c_k>0?Source says solvedFormalized