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
Collection coverage

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

NumberQuestionOpen
#19No statement retained — open to read what the source holdsdecidableNo formal declaration
#57No statement retained — open to read what the source holdsprovedNo formal declaration
#58No statement retained — open to read what the source holdsprovedNo formal declaration
#63No statement retained — open to read what the source holdsprovedNo 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?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 - ε)?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?openFormalized
#110No statement retained — open to read what the source holdsdisprovedNo formal declaration
#111No statement retained — open to read what the source holdsopenNo 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?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.openFormalized
#625No statement retained — open to read what the source holdsopenNo formal declaration
#626No statement retained — open to read what the source holdsopenNo formal declaration
#627No statement retained — open to read what the source holdsopenNo 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?falsifiableFormalized
#629No statement retained — open to read what the source holdsopenNo formal declaration
#630No statement retained — open to read what the source holdsprovedNo formal declaration
#631No statement retained — open to read what the source holdsprovedNo formal declaration
#632No statement retained — open to read what the source holdsdisprovedNo formal declaration
#640No statement retained — open to read what the source holdsopenNo formal declaration
#704No statement retained — open to read what the source holdsopenNo formal declaration
#705Let GG be a finite unit distance graph in \mamthbbR2\mamthbb{R}^2. Is there some kk such that if GG has girth ≥k≥ k, then χ(G)≤3\chi(G) ≤ 3?disprovedFormalized
#706No statement retained — open to read what the source holdsopenNo formal declaration
#736No statement retained — open to read what the source holdsnot provableNo formal declaration
#737No statement retained — open to read what the source holdsprovedNo formal declaration
#738No statement retained — open to read what the source holdsopenNo formal declaration
#739No statement retained — open to read what the source holdsnot 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?openFormalized
#744No statement retained — open to read what the source holdsdisprovedNo 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)?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?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.disproved (Lean)Formalized
#758No statement retained — open to read what the source holdssolvedNo formal declaration
#759No statement retained — open to read what the source holdssolvedNo 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.proved (Lean)Formalized
#761No statement retained — open to read what the source holdsopenNo 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.disproved (Lean)Formalized
#780No statement retained — open to read what the source holdsprovedNo formal declaration
#797No statement retained — open to read what the source holdsprovedNo formal declaration
#799No statement retained — open to read what the source holdsprovedNo formal declaration
#832No statement retained — open to read what the source holdsdisprovedNo formal declaration
#833No statement retained — open to read what the source holdsprovedNo formal declaration
#836No statement retained — open to read what the source holdsopenNo formal declaration
#842No statement retained — open to read what the source holdsprovedNo formal declaration
#917No statement retained — open to read what the source holdsopenNo 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?openFormalized
#919No statement retained — open to read what the source holdsopenNo 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?solvedFormalized

Search problems.science

Find a Problem, Result, source, or page