Conjectured by Erdős, Faber, and Lovász (apparently 'at a party in Boulder, Colarado in September 1972' [Er81]).

Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman [Hi81] proved the conjecture for $n<10$. Various special cases have been established by Romero and Sáchez-Arroyo [RoSa07], Araujo-Pardo and Vázquez-\'{A}vila [ArVa16], and Alesandroi [Al21].

Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.

In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.

In [Er93] Erdős and Füredi conjecture the generalisation that if $G$ is the union of $n$ copies of $K_n$, which pairwise intersect in at most $k$ vertices, then $\chi(G)\leq kn$. This has been proved for all sufficiently large $n$ (not depending on $k$) by Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO24]. Furthermore, Horák and Tuza [HoTu90] proved that if $\chi(G) \leq n^{3/2}$ if $G$ is the union of $n$ copies of $K_n$, and hence this conjecture also holds whenever $k<\sqrt{n}$.

View the LaTeX source

This page was last edited 06 December 2025.

Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density, and in [Er95d] and [Er96] he speculates whether the upper density (or even upper logarithmic density) must be $\geq 1/2$.

The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].

View the LaTeX source

Conjectured by Bollobás and Erdős. Bollobás and Shelah have confirmed this for $k=1$. Proved by Gyárfás [Gy92], who proved the stronger result that, if $G$ is 2-connected, then $G$ is either $K_{2k+2}$ or contains a vertex of degree at most $2k$.

A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.

View the LaTeX source

Conjectured by Mihók and Erdős. It is likely that $2^n$ can be replaced by any sufficiently quickly growing sequence (e.g. the squares).

David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).

Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.

See also [64].

View the LaTeX source

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82].

Rödl [Ro82] has proved this for hypergraphs, and also proved there is such a graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed constant $\epsilon>0$.

It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$ (see [111]).

View the LaTeX source

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. In [Er95d] Erdős suggests this may even be true with an independent set of size $\gg n$.

See also [750].

View the LaTeX source

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $r=4$ case (see [923]). The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.

In [Er79b] Erdős also asks whether\[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]See also the entry in the graphs problem collection and [740] for the infinitary version.

View the LaTeX source

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number $\aleph_0$.

A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.

In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.

Shelah [KoSh05] proved that it is consistent that the answer is no. Lambie-Hanson [La20] constructed a counterexample in ZFC.

View the LaTeX source

This page was last edited 01 October 2025.

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.

On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.

See also [74].

View the LaTeX source

Asked by Andrásfai and Erdős. Erdős [Er97b] also asked where such a graph could contain an infinite complete graph, but this is impossible by an earlier result of Anning and Erdős [AnEr45].

See also [213].

View the LaTeX source

Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]. Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq \aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle.

View the LaTeX source

A problem of Erdős and Gimbel (see also [Gi16]). At a conference on random graphs in Poznan, Poland (most likely in 1989) Erdős offered \$100 for a proof that this is true, and \$1000 for a proof that this is false (although later told Gimbel that \$1000 was perhaps too much).

It is known that almost surely\[\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.\](The final upper bound is due to Bollobás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)

Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability,\[\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.\]Heckel [He24c] further proved that, for any $\epsilon>0$, we have\[\chi(G) -\zeta(G) \geq n^{1-\epsilon}\]for roughly $95\%$ of all $n$.

View the LaTeX source

It is known that\[\frac{1}{4\log k}\log n\leq g_k(n) \leq \frac{2}{\log(k-2)}\log n+1,\]the lower bound due to Kostochka [Ko88] and the upper bound to Erdős [Er59b].

Erdős [Er59b] proved that\[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\gg \frac{1}{m}\]and, for odd $m$,\[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\leq \frac{2}{m+1},\]and conjectured this is sharp. He had no good guess for the value of the limit for even $m$, other that it should lie in $[\frac{2}{m+2},\frac{2}{m}]$, but could not prove this even for $m=4$.

See also the entry in the graphs problem collection.

View the LaTeX source

Tutte and Zykov [Zy52] independently proved that for every $k$ there is a graph with $\omega(G)=2$ and $\chi(G)=k$. Erdős [Er61d] proved that for every $n$ there is a graph on $n$ vertices with $\omega(G)=2$ and $\chi(G)\gg n^{1/2}/\log n$, whence $f(n) \gg n^{1/2}/\log n$.

Erdős [Er67c] proved that\[f(n) \asymp \frac{n}{(\log n)^2}\]and that the limit in question, if it exists, must be in\[(\log 2)^2\cdot [1/4,1].\]See also the entry in the graphs problem collection.

View the LaTeX source

This property is sometimes called being $(a,b)$-splittable. A question of Erdős and Lovász (often called the Erdős-Lovász Tihany conjecture). Erdős [Er68b] originally asked about $a=b=3$ which was proved by Brown and Jung [BrJu69] (who in fact prove that $G$ must contain two vertex disjoint odd cycles).

Balogh, Kostochka, Prince, and Stiebitz [BKPS09] have proved the full conjecture for quasi-line graphs and graphs with independence number $2$.

For more partial results in this direction see the comprehensive survey of this problem by Song [So22].

See also the entry in the graphs problem collection.

View the LaTeX source

This page was last edited 06 December 2025.

A problem of Erdős, Rubin, and Taylor [ERT80], who proved that\[2^{k-1}<n(k) <k^22^{k+2}.\]They also prove that if $m(k)$ is the size of the smallest family of $k$-sets without property B (i.e. the smallest number of $k$-sets in a graph with chromatic number $3$) then $m(k)\leq n(k)\leq m(k+1)$. Bounds on $m(k)$ are the subject of [901]. The lower bounds on $m(k)$ by Radhakrishnan and Srinivasan [RaSr00] imply that\[2^k \left(\frac{k}{\log k}\right)^{1/2}\ll n(k).\]Erdős, Rubin, and Taylor [ERT80] proved $n(2)=6$ and Hanson, MacGillivray, and Toft [HMT96] proved $n(3)=14$ and\[n(k) \leq kn(k-2)+2^k.\]See also the entry in the graphs problem collection.

View the LaTeX source

This page was last edited 28 October 2025.

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer is yes, proved by Alon and Tarsi [AlTa92].

See also [631].

View the LaTeX source

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer to both is yes: Thomassen [Th94] proved that $\chi_L(G)\leq 5$ if $G$ is planar, and Voigt [Vo93] constructed a planar graph with $\chi_L(G)=5$. A simpler construction was given by Gutner [Gu96].

See also [630].

View the LaTeX source

A problem of Erdős, Rubin, and Taylor [ERT80]. Note that $G$ is $(a,1)$-choosable corresponds to being $a$-choosable, that is, the list chromatic number satisfies $\chi_L(G)\leq a$.

This is false: Dvořák, Hu, and Sereni [DHS19] construct a graph which is $(4,1)$-choosable but not $(8,2)$-choosable.

See also the entry in the graphs problem collection.

View the LaTeX source

A problem of Erdős and Hajnal.

This is trivial when $k=3$, since any non-bipartite graph contains an odd cycle, and all odd cycles have chromatic number $3$.

Steiner has observed in the comments that this is equivalent to the problem in which we replace 'odd cycle' with 'path'.

View the LaTeX source

This page was last edited 22 January 2026.

A generalisation of the Hadwiger-Nelson problem (which addresses $n=2$). Frankl and Wilson [FrWi81] proved exponential growth:\[\chi(G_n) \geq (1+o(1))1.2^n.\]The trivial colouring (by tiling with cubes) gives\[\chi(G_n) \leq (2+\sqrt{n})^n.\]Larman and Rogers [LaRo72] improved this to\[\chi(G_n) \leq (3+o(1))^n,\]and conjecture the truth may be $(2^{3/2}+o(1))^n$. Prosanov [Pr20] has given an alternative proof of this upper bound.


See also [508], [705], and [706].

View the LaTeX source

The maximal value of $\chi(G)$ (without a girth condition) is the Hadwiger-Nelson problem. There are unit distance graphs (e.g. the Moser spindle) with $\chi(G)=4$ of girth $3$. de Grey [dG18] has constructed a unit distance graph $G$ with $\chi(G)=5$. (I do not know what the largest girth achieved is by these recent constructions.)

Wormald [Wo79] has constructed a unit distance graph with $\chi(G)=4$ and girth $5$, with $6448$ vertices. O'Donnell [OD94] has constructed a unit distance graph with $\chi(G)=4$ and girth $4$, with $56$ vertices. Chilakamarri [Ch95] has constructed an infinite family of unit distance graphs with $\chi(G)=4$ and girth $4$, the smallest of which has $47$ vertices.


See also [508], [704], and [706].

View the LaTeX source

The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$.


See also [508], [704], and [705].

View the LaTeX source

A conjecture of Walter Taylor. The more general problem replaces $\aleph_1$ with any uncountable cardinal $\kappa$.

More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.

Komjáth [KoSh05] proved that it is consistent that the answer is no, in that there exists a graph $G$ with chromatic number $\aleph_1$ such that if $H$ is any graph all of whose finite subgraphs are subgraphs of $G$ then $H$ has chromatic number $\leq \aleph_2$.

View the LaTeX source

This page was last edited 01 October 2025.

A problem of Erdős, Hajnal, and Shelah [EHS74], who proved that $G$ must contain all sufficiently large cycles (see [594]).

This is true, and was proved by Thomassen [Th83].

View the LaTeX source

This page was last edited 01 October 2025.

A conjecture of Gyárfás.

View the LaTeX source

A question of Galvin [Ga73], who proved that this is true with $\mathfrak{m}=\aleph_0$. Galvin also proved that the stronger version of this statement, in which the subgraph is induced, implies $2^{\mathfrak{k}}<2^{\mathfrak{n}}$ for all cardinals $\mathfrak{k}<\mathfrak{n}$.

Komjáth [Ko88b] proved it is consistent that\[2^{\aleph_0}=2^{\aleph_1}=2^{\aleph_2}=\aleph_3\]and that there exist graphs which fail this property (with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$).

Shelah [Sh90] proved that, assuming the axiom of constructibility, the answer is yes with $\mathfrak{m}=\aleph_2$ and $\mathfrak{n}=\aleph_1$.

It remains open whether the answer to this question is yes assuming the Generalized Continuum Hypothesis, for example.

View the LaTeX source

This page was last edited 01 October 2025.

A question of Erdős and Hajnal. Rödl proved this is true if $\mathfrak{m}=\aleph_0$ and $r=3$ (see [108] for the finitary version).

More generally, Erdős and Hajnal asked must there exist (for every cardinal $\mathfrak{m}$ and integer $r$) some $f_r(\mathfrak{m})$ such that every graph with chromatic number $\geq f_r(\mathfrak{m})$ contains a subgraph with chromatic number $\mathfrak{m}$ with no odd cycle of length $\leq r$?

Erdős [Er95d] claimed that even the $r=3$ case of this is open: must every graph with sufficiently large chromatic number contain a triangle free graph with chromatic number $\mathfrak{m}$?

In [Er81] Erdős also asks the same question but with girth (i.e. the subgraph does not contain any cycle at all of length $\leq C$).

View the LaTeX source

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Odd cycles show that $f_3(n)=1$, but they expected $f_4(n)\to \infty$. Gallai [Ga68] gave a construction which shows\[f_4(n) \ll n^{1/2},\]and Lovász extended this to show\[f_k(n) \ll n^{1-\frac{1}{k-2}}.\]This conjecture was disproved by Rödl and Tuza [RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).

View the LaTeX source

This page was last edited 01 January 2026.

In [Er69b] Erdős conjectures this for $f(m)=\epsilon m$ for any fixed $\epsilon>0$. This follows from a result of Erdős, Hajnal, and Szemerédi [EHS82], as described by msellke in the comments.

In [ErHa67b] Erdős and Hajnal prove this for $f(m)\geq cm$ for all $c>1/4$.

See also [75].

View the LaTeX source

This page was last edited 14 October 2025.

The answer is no: Bondy and Vince [BoVi98] proved that every graph with minimum degree at least $3$ has two cycles whose lengths differ by at most $2$, and hence the same is true for every graph with chromatic number $4$.

View the LaTeX source

A problem of Erdős, Rubin, and Taylor.

The answer is no: Alon [Al92] proved that, for every $n$, there exists a graph $G$ on $n$ vertices such that\[\chi_L(G)+\chi_L(G^c)\ll (n\log n)^{1/2},\]where the implied constant is absolute.

View the LaTeX source

A question of Erdős and Gimbel, who knew that $4\leq z(12)\leq 5$ and $5\leq z(15)\leq 6$. The equality $z(12)=4$ would follow from proving that if $G$ is a graph on $12$ vertices such that both $G$ and its complement are $K_4$-free then either $\chi(G)\leq 4$ or $\chi(G^c)\leq 4$.

In fact there do exist such graphs - Bhavik Mehta found computationally that there is exactly one (up to taking the complement) graph on $12$ vertices such that both $G$ and its complement are $K_4$-free with chromatic number $\geq 5$. This graph was explicitly checked to have cochromatic number $4$, and hence this proves that indeed $z(12)=4$.

The values of $z(n)$ are now known for $1\leq n\leq 19$:\[1,1,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,6.\](The only significant difficulty here is proving $z(12)=4$ - the others follow from easy inductive arguments and the facts that $R(3)=6$ and $R(4)=18$.)
It is unknown whether $z(20)=6$ or $7$.

Gimbel [Gi86] has shown that $z(n) \asymp \frac{n}{\log n}$.

View the LaTeX source

A problem of Erdős and Gimbel. Gimbel [Gi86] proved that\[\frac{\sqrt{n}}{\log n}\ll z(S_n) \ll \sqrt{n}.\]Solved by Gimbel and Thomassen [GiTh97], who proved\[z(S_n) \asymp \frac{\sqrt{n}}{\log n}.\]

View the LaTeX source

A problem of Erdős and Gimbel, who proved that there must exist a subgraph $H$ with\[\zeta(H) \gg \left(\frac{m}{\log m}\right)^{1/2}.\]The proposed bound would be best possible, as shown by taking $G$ to be a complete graph.

The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].

View the LaTeX source

The first question is due to Erdős and Neumann-Lara. The second question is due to Erdős and Gimbel. A positive answer to the second question implies a positive answer to the first via the bound mentioned in [760].

View the LaTeX source

A conjecture of Erdős, Gimbel, and Straight [EGS90], who proved that for every $n>2$ there exists some $f(n)$ such that if $G$ contains no clique on $n$ vertices then $\chi(G)\leq \zeta(G)+f(n)$.

This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.

View the LaTeX source

In other words, this problem asks to determine the chromatic number of the Kneser graph. This would be best possible: if $n=kr-1+(t-1)(k-1)$ then decomposing $[n]$ as one set $X_1$ of size $kr-1$ and $t-1$ sets $X_2,\ldots,X_{t}$ of size $k-1$, a colouring without $k$ pairwise disjoint edges is given colouring all subsets of $X_0$ in colour $1$ and assigning an edge with colour $2\leq i\leq t$ if $i$ is minimal such that $X_i$ intersects the edge.

When $k=2$ this was conjectured by Kneser and proved by Lovász [Lo78]. The general case was proved by Alon, Frankl, and Lovász [AFL86].

View the LaTeX source

It is easy to see that $f(d)\leq d^2+1$ using a greedy colouring. Erdős had shown $f(d)\geq d^{4/3-o(1)}$.

Resolved by Alon, McDiarmid, and Reed [AMR91] who showed\[\frac{d^{4/3}}{(\log d)^{1/3}}\ll f(d) \ll d^{4/3}.\]

View the LaTeX source

A problem of Erdős, Rubin and Taylor.

The answer is yes: Alon [Al92] proved that in fact the random graph on $n$ vertices with edge probability $1/2$ has\[\chi_L(G) \ll \frac{\log\log n}{\log n}n\]almost surely. Alon, Krivelevich, and Sudakov [AKS99] improved this to\[\chi_L(G) \asymp \frac{n}{\log n}\]almost surely.

View the LaTeX source

When $r=2$ it is a classical fact that chromatic number $k$ implies at least $\binom{k}{2}$ edges. Erdős asked for $k$ to be large in this conjecture since he knew it to be false for $r=k=3$, as witnessed by the Steiner triples with $7$ vertices and $7$ edges.

This was disproved by Alon [Al85], who proved, for example, that there exists some absolute constant $C>0$ such that if $r\geq C$ and $k\geq Cr$ then there exists an $r$-uniform hypergraph with chromatic number $\geq k$ with at most\[\leq (7/8)^r\binom{(r-1)(k-1)+1}{r}\]many edges.

In general, Alon gave an upper bound for the minimal number of edges using Turán numbers. Using known bounds for Turán numbers then suffices to disprove this conjecture for all $r\geq 4$. The validity of this conjecture for $r=3$ remains open.

If $m(r,k)$ denotes the minimal number of edges of any $r$-uniform hypergraph with chromatic number $>k$ then Akolzin and Shabanov [AkSh16] have proved\[\frac{r}{\log r}k^r \ll m(r,k) \ll (r^3\log r) k^r,\]where the implied constants are absolute. Cherkashin and Petrov [ChPe20] have proved that, for fixed $r$, $m(r,k)/k^r$ converges to some limit as $k\to \infty$.

View the LaTeX source

In general, determine the largest integer $f(r)$ such that every $r$-uniform hypergraph with chromatic number $3$ has a vertex contained in at least $f(r)$ many edges. It is easy to see that $f(2)=2$ and $f(3)=3$. Erdős did not know the value of $f(4)$.

This was solved by Erdős and Lovász [ErLo75], who proved in particular that there is a vertex contained in at least\[\frac{2^{r-1}}{4r}\]many edges.

View the LaTeX source

A problem of Erdős and Shelah. The Fano geometry gives an example where there are no two edges which meet in $r-1$ vertices. Are there any other examples?

Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.

Alon has provided the following counterexample to the first question: as vertices take two sets $X$ and $Y$ of sizes $2r-2$ and $\frac{1}{2}\binom{2r-2}{r-1}$ respectively, where $Y$ corresponds to all partitions of $X$ into two equal parts. The edges are all subsets of $X$ of size $r$, and also all sets consisting of a subset of $X$ of size $r-1$ together with the unique element of $Y$ corresponding to the induced partition of $X$.

This hypergraph is intersecting, its chromatic number is $3$, and it has $\asymp 4^r/\sqrt{r}$ many vertices.

View the LaTeX source

The answer is yes, proved by Fleischner and Stiebitz [FlSt92].

View the LaTeX source

Erdős [Er93] wrote 'I learned of this definition from Dirac in 1949 and immediately asked whether $f_k(n)=o(n^2)$. To my great surprise Dirac constructed a $6$ critical graph on $n$ vertices with more than $\frac{n^2}{4}$ edges.' In fact Dirac [Di52] proved\[f_6(4n+2) \geq 4n^2+8n+3,\]as witnessed by taking two disjoint copies of $C_{2n+1}$ and adding all edges between them.

Erdős [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that\[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.\]Toft [To70] proved that $f_k(n)\gg_k n^2$ for $k\geq 4$.

Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of $n$ such that\[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2\]where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and $\delta_k\equiv 24/69$ if $k\equiv 2\pmod{3}$, which disproves Erdős' conjectured asympotic for $k\not\equiv 0\pmod{3}$.

Stiebitz also proved the general upper bound\[f_k(n) < \mathrm{ex}(n;K_{k-1})\sim \frac{1}{2}\left(1-\frac{1}{k-2}\right)n^2\]for large $n$. Luo, Ma, and Yang [LMY23] have improved this upper bound to\[f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2\]See also [944] and [1032].

View the LaTeX source

A question of Erdős and Hajnal [ErHa68b], who proved that for every finite $k$ there is a graph with chromatic number $\aleph_1$ where each subgraph on less than $\aleph_k$ vertices has chromatic number $\leq \aleph_0$.

In [Er69b] it is asked with chromatic number $=\aleph_0$, but in the comments louisd observes this is (assuming subgraph and not induced subgraph was intended) trivially impossible, and hence presumably the problem was intended as written here (which is how it is posed in [ErHa68b]).

View the LaTeX source

This page was last edited 24 October 2025.

This question was inspired by a theorem of Babai, that if $G$ is a graph on a well-ordered set with chromatic number $\geq \aleph_0$ there is a subgraph on vertices with order-type $\omega$ with chromatic number $\aleph_0$.

Erdős and Hajnal showed this does not generalise to higher cardinals - they (see [Er69b]) constructed a set on $\omega_1^2$ with chromatic number $\aleph_1$ such that every strictly smaller subgraph has chromatic number $\leq \aleph_0$ as follows: the vertices of $G$ are the pairs $(x_\alpha,y_\beta)$ for $1\leq \alpha,\beta <\omega_1$, ordered lexicographically. We connect $(x_{\alpha_1},y_{\beta_1})$ and $(x_{\alpha_2},y_{\beta_2})$ if and only if $\alpha_1<\alpha_2$ and $\beta_1<\beta_2$.

A similar construction produces a graph on $\omega_2^2$ with chromatic number $\aleph_2$ such that every smaller subgraph has chromatic number $\leq \aleph_1$.

View the LaTeX source

Graver and Yackel [GrYa68] proved that\[f_k(n) \ll \left(n\frac{\log\log n}{\log n}\right)^{1-\frac{1}{k-1}}.\]It is known that $f_3(n)\asymp (n/\log n)^{1/2}$ (see [1104]).

The lower bound $R(4,m) \gg m^3/(\log m)^4$ of Mattheus and Verstraete [MaVe23] (see [166]) implies\[f_4(n) \gg \frac{n^{2/3}}{(\log n)^{4/3}}.\]A positive answer to this question would follow from [986]. The known bounds for that problem imply\[f_k(n) \gg \frac{n^{1-\frac{2}{k+1}}}{(\log n)^{c_k}}.\]See [1104] (and also [1013]) for the case $k=3$.

View the LaTeX source

This page was last edited 21 January 2026.

A question of Erdős and Gallai. Gallai [Ga63] proved that\[f_4(n) \gg n^{1/2}\]and Erdős (unpublished) proved $f_4(n) \ll n^{1/2}$.

This was proved for all $k\geq 4$ by Kierstead, Szemerédi, and Trotter [KST84].

View the LaTeX source

A question of Erdős and Hajnal [ErHa67b]. The case $k=0$ is trivial, but they could not prove this even for $k=1$.

This is true, and was proved by Folkman [Fo70b].

See also [73].

View the LaTeX source

This is true, as shown by Rödl [Ro77].

See [108] for a more general question.

View the LaTeX source

A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical.

This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open.

Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$. Skottova and Steiner [SkSt25] have improved this, proving that such graphs exist for all $k\geq 5$ and $r\geq 1$. The only remaining open case is $k=4$ (even the case $k=4$ and $r=1$ remains open).


Erdős also asked a stronger quantitative form of this question: let $f_k(n)$ denote the largest $r\geq 1$ such that there exists a $k$-vertex-critical graph on $n$ vertices such that no set of at most $r$ edges is critical. He then asks whether $f_k(n)\to \infty$ as $n\to \infty$. Skottova and Steiner [SkSt25] have proved this for $k\geq 5$, establishing the bounds\[n^{1/3}\ll_k f_k(n) \ll_k \frac{n}{(\log n)^C}\]for all $k\geq 5$, where $C>0$ is an absolute constant.

This is Problem 91 in the graph problems collection. See also [917] and [1032].

View the LaTeX source

The function $h_3(k)$ is dual to the function $f(n)$ considered in [1104], in that $h_3(k)= n$ if and only if $n$ is minimal such that $f(n)=k$.

Graver and Yackel [GrYa68] proved\[h_3(k)\gg \frac{\log k}{\log\log k}k^2.\]The bounds for $f(n)$ from [1104] imply\[\left(\frac{1}{2}-o(1)\right)k^2\log k\leq h_3(k) \leq (1+o(1))k^2\log k.\]See also [920] for a generalisation to $K_r$-free graphs.

View the LaTeX source

This page was last edited 21 January 2026.

In [Er93] Erdős said he asked this 'more than 20 years ago'.

Dirac gave an example of a $6$-chromatic critical graph with minimum degree $>n/2$. This problem is also open for $5$-chromatic critical graphs.

Simonovits [Si72] and Toft [To72] independently constructed $4$-chromatic critical graphs with minimum degree $\gg n^{1/3}$. Toft conjectured that a $4$-chromatic critical graph on $n$ vertices has at least $(\frac{5}{3}+o(1))n$ vertices, and has examples to show this would be the best possible.

See also [917] and [944].

View the LaTeX source

I do not think this was originally a question of Erdős - it appears in [BoPi24] as a 'version of the Erdős-Hajnal problem' (which is [1067]).

I could not in fact find this in the paper of Erdős and Hajnal [ErHa66], however, and hence the first place it appears may in fact be in [BoPi24]. In hindsight this should not have been included as a separate problem, but this has been discovered too late, and so we must leave it here.

We say a graph is infinitely (vertex) connected if any two vertices are connected by infinitely many pairwise vertex-disjoint paths.

Soukup [So15] constructed a graph with uncountable chromatic number in which every uncountable set is finitely vertex-connected. A simpler construction was given by Bowler and Pitz [BoPi24].

See also [1067].

View the LaTeX source

This page was last edited 18 January 2026.

Erdős originally asked about the existence of just one diagonal, which is true, and was proved by Larson [La79]. In fact Larson proved the following stronger conjecture of Bollobás and Erdős: if $G$ is a $K_4$-free graph containing no odd cycle with a diagonal then either $G$ is bipartite, or $G$ contains a cut vertex, or $G$ contains a vertex with degree $\leq 2$.

The pentagonal wheel shows that three diagonals are not guaranteed.

The first question was solved in the affirmative by Voss [Vo82].

View the LaTeX source

This page was last edited 06 December 2025.

A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from, [744].

Tang notes in the comments that a construction of Rödl [Ro82] disproves the first question, so that $f_2(n)\not\gg n$.

View the LaTeX source

This page was last edited 06 December 2025.

The best bounds available are\[(1-o(1))(n/\log n)^{1/2}\leq f(n) \leq (2+o(1))(n/\log n)^{1/2}.\]The upper bound is due to Davies and Illingworth [DaIl22], the lower bound follows from a construction of Hefty, Horn, King, and Pfender [HHKP25].

One can ask a similar question for the maximum possible chromatic number of a triangle-free graph on $m$ edges. Let this be $g(m)$. Davies and Illingworth [DaIl22] prove\[g(m) \leq (3^{5/3}+o(1))\left(\frac{m}{(\log m)^2}\right)^{1/3}.\]Kim [Ki95] gave a construction which implies $g(m) \gg (m/(\log m)^2)^{1/3}$.

The function $f(n)$ is the inverse to the function $h_3(k)$ considered in [1013].

A generalisation of $f(n)$ is considered in [920].

View the LaTeX source

This page was last edited 21 January 2026.