Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
If \(G\) is an edge-disjoint union of \(n\) copies of \(K_n\), then is \(\chi(G) = n\)?
If \(G\) is a graph with infinite chromatic number and \(a_1 < a_2 < \cdots\) are lengths of the odd cycles of \(G\) then \(\sum \frac{1}{a_i} = \infty\). Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20].…
If \(G\) is a graph which contains odd cycles of \(\leq k\) different lengths then \(\chi(G)\leq 2k+2\), with equality if and only if \(G\) contains \(K_{2k+2}\). Conjectured by Bollobás and Erdős. Proved by Gyárfás [Gy92].
Does every graph with infinite chromatic number contain a cycle of length \(2^n\) for infinitely many \(n\)? Conjectured by Mihók and Erdős. Solved affirmatively following the work of Liu and Montgomery [LiMo20]. The linked formal proof…
Let \(f(n)\to \infty\) possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on \(n\) vertices can be made bipartite by deleting at most \(f(n)\) edges? The answer is no. A machine-checked…
Is 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 - ε)?
For 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?
Let \(A\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 \(A\), where two vertices are joined by an edge if and only if they are…
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
Let \(k \geq 4\) and let \(g_k(n)\) denote the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) and girth \(> m\) (i.e. containing no cycle of length \(\leq m\)). Does…
Let \(\omega(G)\) denote the clique number of \(G\) and \(\chi(G)\) the chromatic number. If \(f(n)\) is the maximum value of \(\chi(G)/\omega(G)\), as \(G\) ranges over all graphs on \(n\) vertices, then does…
Erdős-Lovász Tihany Conjecture
Let \(G\) be a graph with chromatic number \(k\) containing no \(K_k\). If \(a,b\geq 2\) and \(a+b=k+1\) then must there exist two disjoint subgraphs of \(G\) with chromatic numbers \(\geq a\) and \(\geq b\) respectively?
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
For every \(k \geq 3\), does there exist \(f(k)\) such that every finite graph of chromatic number at least \(f(k)\) has an odd cycle whose vertices induce a graph of chromatic number at least \(k\)? The cycle may have chords in the…
Does \(\chi(G_n)\) grow exponentially in \(n\)? Yes: Frankl and Wilson [FrWi81] proved an exponential lower bound and Larman and Rogers [LaRo72] proved an exponential upper bound. Here exponential growth means that there are constants…
Let \(G\) be a finite unit distance graph in \(\mamthbb{R}^2\). Is there some \(k\) such that if \(G\) has girth \(≥ k\), then \(\chi(G) ≤ 3\)? The general case was solved by O'Donnell [OD99], who constructed finite unit distance graphs…
Let \(\mathfrak{m}\) be an infinite cardinal and \(G\) be a graph with chromatic number \(\mathfrak{m}\). Let \(r\geq 1\). Must \(G\) contain a subgraph of chromatic number \(\mathfrak{m}\) which does not contain any odd cycle of length…
Let \(f(m)\) be some function such that \(f(m)\to \infty\) as \(m\to \infty\). Does there exist a graph \(G\) of infinite chromatic number such that every subgraph on \(m\) vertices contains an independent set of size at least…
Let \(G\) be a graph with chromatic number \(\chi(G)=4\). If \(m_1<m_2<\cdots\) are the lengths of the cycles in \(G\) then can \(\min(m_{i+1}-m_i)\) be arbitrarily large? The answer is no: Bondy and Vince [BoVi98] proved that every graph…
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or independent set. If \(G\) is a graph with…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or empty graph. Is it true that if \(G\) has no…
Suppose \(n\geq kr+(t-1)(k-1)\) and the edges of the complete \(r\)-uniform hypergraph on \(n\) vertices are \(t\)-coloured. Prove that some colour class must contain \(k\) pairwise disjoint edges. In other words, this problem asks to…
Let \(r\geq 3\) and \(k\) be sufficiently large in terms of \(r\). Is it true that every \(r\)-uniform hypergraph with chromatic number \(k\) has at least \[\binom{(r-1)(k-1)+1}{r}\] edges, with equality only for the complete graph on…
Does there exist an absolute constant \(c>0\) such that, for all \(r\geq 2\), in any \(r\)-uniform hypergraph with chromatic number \(3\) there is a vertex contained in at least \((1+c)^r\) many edges? This was solved by Erdős and Lovász…
Let \(r\geq 2\) and let \(G\) be an intersecting \(r\)-uniform hypergraph with chromatic number \(3\). Must \(G\) contain \(O(r^2)\) many vertices? Vertices are counted in the union of the edges, so isolated vertices are excluded. Alon has…
Let \(G\) be a graph on \(3n\) vertices formed by taking \(n\) vertex disjoint triangles and adding a Hamiltonian cycle (with all new edges) between these vertices. Does \(G\) have chromatic number at most \(3\)? The answer is yes, proved…
Is it true that, for \(k\geq 4\), \(f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}\) for some constant \(c_k>0\)? This problem follows immediately from Mattheus and Verstraete's lower bound [MaVe23] for k = 4 and Bradač's lower…
Let \(k\geq 4\) and let \(f_k(n)\) be the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) in which every odd cycle has length \(> m\). Then \[f_k(n) \asymp n^{\frac{1}{k-2}}.\] A question of Erdős and…
Let \(k\geq 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\geq (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) have chromatic number at most \(k+2\)? A question of…
Is it true that, for every \(k\), there is some \(f(k)\) such that if \(G\) has chromatic number \(\geq f(k)\) then \(G\) contains a triangle-free subgraph with chromatic number \(\geq k\)? This is true, as shown by Rödl [Ro77].
Let \(k \ge 4\) and \(r\ge 1\). Must there exist a graph \(G\) with chromatic number \(k\) such that every vertex is critical, yet every critical set of edges has size \(>r\)?
Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph which is infinitely connected?
Is it true that \(f_2(n) \gg n\)? Disproved by Rödl, who showed \(f_r(n) = o(n)\) for all fixed \(r \geq 2\). A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from,…
Let \(\kappa\) be an uncountable cardinal. Must there exist a cardinal \(\lambda\) such that every graph with chromatic number \(\lambda\) contains a triangle-free subgraph with chromatic number \(\kappa\)? Shelah proved that a negative…
Let \(G\) be a finite \(3\)-uniform hypergraph, and let \(F_G(\kappa)\) denote the collection of \(3\)-uniform hypergraphs with chromatic number \(\kappa\) not containing \(G\). If \(F_G(\aleph_1)\) is not empty then there exists…