SOLVED - $500

If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$?

SOLVED

Let $\epsilon>0$ and $n$ be sufficiently large depending on $\epsilon$. Is there a graph on $n$ vertices with $\geq n^2/8$ many edges which contains no $K_4$ such that the largest independent set has size at most $\epsilon n$?

In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that (for sufficiently large $n$)
\[\mathrm{rt}(n; 4,\epsilon n)\geq n^2/8?\]

Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]

See also [615].

OPEN

Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?

The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky [BCL21], who proved that deleting at most $1.064n^2$ edges suffices.

SOLVED

Does every triangle-free graph on $5n$ vertices contain at most $n^5$ copies of $C_5$?

Győri proved this with $1.03n^5$, which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami, Hladky, Král, Norine, and Razborov [HHKNR13].

SOLVED

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 Hajnal and Erdős and solved by Liu and Montgomery [LiMo20]. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

SOLVED

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. 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.

SOLVED

Is it true that the number of graphs on $n$ vertices which do not contain $G$ is
\[\leq 2^{(1+o(1))\mathrm{ex}(n;G)}?\]

If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [ErFrRo86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least
\[2^{(1+c)\mathrm{ex}(n;C_6)}\]
such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of
\[2^{O(\mathrm{ex}(n;G))}\]
holds for all $G$.

OPEN

Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?

Conjectured by Erdős and Simonovits, who could not even prove that at least $2$ copies of $C_4$ are guaranteed.

He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.

OPEN

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n^c$ vertices?

OPEN

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) which is a subgraph of both $G_1$ and $G_2$?

Erdős, Hajnal, and Shelah have shown that $G_1$ and $G_2$ must both contain all sufficiently large cycles.

OPEN - $1000

Does every graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?

Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

OPEN

Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is the sum $\sum\frac{1}{a_i}$ minimised when $G$ is a complete bipartite graph?

A problem of Erdős and Hajnal. Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.

SOLVED

Is it true that for every pair $a,b\geq 1$ such that either $a$ is even or both $a$ and $b$ are odd then there is $c=c(a,b)$ such that every graph with average degree at least $c$ contains a cycle whose length is $\equiv a\pmod{b}$?

This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(a,b)$ is unknown.

SOLVED - $100

Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?

Bollobás proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers. Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although conjectures that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

SOLVED

Let $k\geq 0$. Let $G$ be a graph on $n$ vertices such that every subgraph $H\subseteq G$ contains an independent set of size $\geq \frac{1}{2}\lvert H\rvert-k$. Must $G$ be the union of a bipartite graph and $O_k(1)$ many vertices?

Proved by Reed [Re99]. (Thanks also to Reed for pointing out that the case $k=0$ is trivial, since if $G$ is not bipartite then $G$ contains an odd cycle.)

OPEN - $500

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?

SOLVED

Is it true that in any $2$-colouring of the edges of $K_n$ there must exist at least
\[(1+o(1))\frac{n^2}{12}\]
many edge-disjoint monochromatic triangles?

Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved
\[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\]
The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23].

OPEN - $100

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$.

Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$.
Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$. Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size
\[\geq 2^{(\log\log n)^{C}}\]
for some constant $C>0$. Li [Li23b] has recently improved this to
\[\geq (\log n)^{C}\]
for some constant $C>0$.

OPEN

We say $G$ is Ramsey size linear if $R(G,H)\ll m$ for all graphs $H$ with $m$ edges and no isolated vertices.

Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?

Asked by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. $K_4$ is the only known example of such a graph.

OPEN

Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain an edge in at least $m$ different triangles. Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or even $f_c(n)\gg \log n$?

A problem of Erdős and Rothschild. Alon and Trotter showed that $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.

See also [600] and the entry in the graphs problem collection.

OPEN

Let $G$ be a chordal graph on $n$ vertices - that is, $G$ has no induced cycles of length greater than $3$. Can the edges of $G$ be partitioned into $n^2/6+O(n)$ many cliques?

Asked by Erdős, Ordman, and Zalcstein [EOZ93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$). The example of all edges between a complete graph on $n/3$ vertices and an empty graph on $2n/3$ vertices show that $n^2/6+O(n)$ is sometimes necessary.

A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.

OPEN

Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$.

Conjectured by Erdős, Fajtlowicz, and Staton. It is known that $F(5)=3$ and $F(7)=4$. Ramsey's theorem implies that $F(n)\gg \log n$. Bollobás observed that $F(n)\ll n^{1/2+o(1)}$. Alon, Krivelevich, and Sudakov [AKS07] have improved this to $n^{1/2}(\log n)^{O(1)}$.

SOLVED

The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\ell \in A$. Let $f(n)$ count the number of possible such $A$. Prove that $f(n)=o(2^n)$.

Conjectured by Erdős and Faudree, who showed that $f(n) > 2^{n/2}$, and further speculate that $f(n)/2^{n/2}\to \infty$. This conjecture was proved by Verstraëte [Ve04], who proved the number of such sets is
\[\ll 2^{n-n^c}\]
for some constant $c>0$.

OPEN

Let $f(n)$ be such that every graph on $n$ vertices with minimal degree $\geq f(n)$ contains a $C_4$. Is it true that $f(n+1)\geq f(n)$?

A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.

OPEN - $100

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with
\[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\]
many edges contains a $C_4$?

The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice.

A similar question can be asked for other even cycles.

OPEN

Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then
\[R(G)>(1-\epsilon)^kR(k)\]
for every graph $G$ with chromatic number $\chi(G)=k$?

Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?

Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.

See also the entry in the graphs problem collection and this second one.

SOLVED - $100

For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$.

Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney [KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.

OPEN

For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number $\geq k$?

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $r=4$ case. 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.\]

OPEN

Is there some $F(n)$ such that every graph with chromatic number $\aleph_1$ has, for all large $n$, a subgraph with chromatic number $n$ on at most $F(n)$ vertices?

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

OPEN

Let $G$ be a graph with chromatic number $\aleph_1$ and let $h(n)=h(n;G)$ be such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h(n)$ edges. What is the behaviour of $h(n)$? Is it true that $h(n)/n\to \infty$?

OPEN

Let $k=k(n,m)$ be minimal such that any directed graph on $k$ vertices must contain either an independent set of size $n$ or a directed path of size $m$. Determine $k(n,m)$.

SOLVED - $250

If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$-degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.

Conjectured by Erdős and Simonovits. Erdős offered \$250 for a proof and \$100 for a counterexample. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that
\[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [146] and [147] and the entry in the graphs problem collection.

SOLVED

Let $f(m)$ be maximal such that every graph with $m$ edges must contain a bipartite graph with
\[\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)\]
edges. Is there an infinite sequence of $m_i$ such that $f(m_i)\to \infty$?

Conjectured by Erdős, Kohayakava, and Gyárfás. Edwards [Ed73] proved that $f(m)\geq 0$ always. Note that $f(\binom{n}{2})= 0$, taking $K_n$. Solved by Alon [Al96], who showed $f(n^2/2)\gg n^{1/2}$, and also showed that $f(m)\ll m^{1/4}$ for all $m$. The best possible constant in $f(m)\leq Cm^{1/4}$ is unknown.

OPEN - $250

Let $G$ be a graph with $10n$ vertices such that every subgraph on $5n$ vertices has more than $2n^2$ many edges. Must $G$ contain a triangle?

A problem of Erdős and Rousseau. The constant $50$ would be best possible as witnessed by a blow-up of $C_5$ or the Petersen graph. Krivelevich [Kr95] has proved this with $n/2$ replaced by $3n/5$ (and $50$ replaced by $25$).

Keevash and Sudakov [KeSu06] have proved this under the additional assumption that $G$ has at most $n^2/12$ edges.

OPEN

Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours. Prove that there is a constant $C=C(r)>1$ such that
\[R(n;3,r) < C^{\sqrt{n}}.\]

Conjectured by Erdős and Gyárfás, who proved the existence of some $C>1$ such that $R(n;3,r)>C^{\sqrt{n}}$. Note that when $r=k=2$ we recover the classic Ramsey numbers. It is likely that for all $r,k\geq 2$ there exists some $C_1,C_2>1$ (depending only on $r$) such that
\[ C_1^{n^{1/k-1}}< R(n;k,r) < C_2^{n^{1/k-1}}.\]
Antonio Girao has pointed out that this problem as written is easily disproved: the obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), as soon as $N \geq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture. Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.

OPEN

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 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?

Asked by Andrásfai and Erdős. It is possible that such a graph could contain an infinite complete graph.

See also [213].

OPEN

Let $f(n)$ be minimal such that every triangle-free graph $G$ with $n$ vertices and diameter $2$ contains a vertex with degree $\geq f(n)$. What is the order of growth of $f(n)$? Does $f(n)/\sqrt{n}\to \infty$?

Asked by Erdős and Pach. Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$, showing that $f(n)=o(n)$ infinitely often. This graph may have the minimal possible $f$, but Erdős encourages the reader to try and find a better graph.

OPEN

Let $\epsilon,\delta>0$ and $n$ sufficiently large in terms of $\epsilon$ and $\delta$. Let $G$ be a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$. Can $G$ be made into a triangle-free graph with diameter $2$ by adding at most $\delta n^2$ edges?

Asked by Erdős and Gyárfás, who proved that this is the case when $G$ has maximum degree $\ll \log n/\log\log n$. A construction of Simonovits shows that this conjecture is false if we just have maximum degree $\leq Cn^{1/2}$, for some large enough $C$.

SOLVED

Let $f(n)$ be the smallest number of colours required to colour the edges of $K_n$ such that every $K_4$ contains at least 5 colours. Determine the size of $f(n)$.

Asked by Erdős and Gyárfás, who proved that
\[\frac{5}{6}(n-1) < f(n)<n,\]
and that $f(9)=8$. Erdős believed the upper bound is closer to the truth. In fact the lower bound is: Bennett, Cushman, Dudek,and Pralat [BCDP22] have shown that
\[f(n) \sim \frac{5}{6}n.\]
Joos and Mubayi [JoMu22] have found a shorter proof of this.

OPEN - $500

If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then
\[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]

Conjectured by Erdős and Simonovits. Open even for $r=3$. Alon, Krivelevich, and Sudakov [AKS03] have proved
\[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\]
They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

SOLVED - $500

If $H$ is bipartite and is not $r$-degenerate, that is, there exists an induced subgraph of $H$ with minimum degree $>r$ then
\[\mathrm{ex}(n;H) > n^{2-\frac{1}{r}+\epsilon}.\]

Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that
\[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

OPEN

Let $G$ be a graph of maximum degree $\Delta$. Is $G$ the union of at most $\tfrac{5}{4}\Delta^2$ sets of strongly independent edges (sets such that the induced subgraph is the union of vertex-disjoint edges)?

Asked by Erdős and Nešetřil. They also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.

OPEN

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let $c(n)$ be the maximum number of minimal cuts a graph on $n$ vertices can have.
Is $c(3m+2)=3^m$? Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?

Asked by Erdős and Nešetřil. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

OPEN

Let $h(n)$ be minimal such that, for every graph $G$ on $n$ vertices, there is a set of vertices $X$ of size $\lvert X\rvert\leq h(n)$ such that every maximal clique (on at least $2$ vertices) in $G$ contains at least one vertex from $X$.
Let $H(n)$ be maximal such that every triangle-free graph on $n$ vertices contains an independent set on $H(n)$ vertices.
Does $h(n)=n-H(n)$?

It is easy to see that $h(n)\leq n-\sqrt{n}$ and that $h(n)\leq n-H(n)$. Conjectured by Erdős and Gallai, who were unable to make progress even assuming $G$ is $K_4$-free. Erdős remarked that this conjecture is 'perhaps completely wrongheaded'.

SOLVED

For any $d\geq 1$ if $H$ is a graph such that every subgraph contains a vertex of degree at most $d$ then $R(H)\ll_d n$.

The Burr-Erdős conjecture. This is equivalent to showing that if $H$ is the union of $c$ forests then $R(H)\ll_c n$, and also that if every subgraph has average degree at most $d$ then $R(H)\ll_d n$. Solved by Lee [Le16], who proved that
\[ R(H) \leq 2^{2^{O(d)}}n.\]

It is known that there exists some constant $c>0$ such that for large $k$
\[c\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.\]
The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AjKoSz80]. The lower bound has been improved to
\[\left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}\]
independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude.

See also [544].

Spencer [Sp77] proved
\[R(4,k) \gg (k\log k)^{5/2}.\]
Ajtai, Komlós, and Szemerédi [AjKoSz80] proved
\[R(4,k) \ll \frac{k^3}{(\log k)^2}.\]
This is true, and was proved by Mattheus and Verstraete [MaVe23], who showed that
\[R(4,k) \gg \frac{k^3}{(\log k)^4}.\]

OPEN

If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges?

A problem of Tuza. It is trivial that $G$ can be made triangle-free after removing at most $3k$ edges. The examples of $K_4$ and $K_5$ show that $2k$ would be best possible.

OPEN

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$. Note that it is trivial that $\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G)$ for every $G\in\mathcal{F}$.

Is it true that, for every $\mathcal{F}$, there exists $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]

A problem of Erdős and Simonovits.

This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.

See also [575] and the entry in the graphs problem collection.

OPEN

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that
\[R(Q_n) \ll 2^n.\]

Conjectured by Burr and Erdős. The trivial bound is
\[R(Q_n) \leq R(K_{2^n})\leq C^{2^n}\]
for some constant $C>1$. This was improved a number of times; the current best bound due to Tikhomirov [Ti22] is
\[R(Q_n)\ll 2^{(2-c)n}\]
for some small constant $c>0$. (In fact $c\approx 0.03656$ is permissible.)

SOLVED

Let $k\geq 3$. What is the maximum number of edges that a graph on $n$ vertices can contain if it does not have a $k$-regular subgraph?

Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu22], who proved that there exists some $C=C(k)>0$ such that any graph on $n$ vertices with at least $Cn\log\log n$ edges contains a $k$-regular subgraph.

A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.

OPEN - $250

Let $R(3;k)$ be the minimal $n$ such that if the edges of $K_n$ are coloured with $k$ colours then there must exist a monochromatic triangle. Determine
\[\lim_{k\to \infty}R(3;k)^{1/k}.\]

Erdős offers \$100 for showing that this limit is finite. An easy pigeonhole argument shows that
\[R(3;k)\leq 2+k(R(3;k-1)-1),\]
from which $R(3;k)\leq \lceil e k!\rceil$ immediately follows. The best-known upper bounds are all of the form $ck!+O(1)$, and arise from this type of inductive relationship and computational bounds for $R(3;k)$ for small $k$. The best-known lower bound (coming from lower bounds for Schur numbers) is due to Exoo [Ex94],
\[R(3;k) \gg (321)^{k/5}.\]

See also [483].

OPEN

Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.

OPEN - $100

We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$. Is there a graph on $n$ vertices with
\[\gg \frac{2^{\binom{n}{2}}}{n!}\]
many distinct unique subgraphs?

A problem of Erdős and Entringer [EnEr72], who constructed a graph with
\[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\]
many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with
\[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\]
many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for a construction and \$25 for a proof that no such construction is possible.

OPEN

What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.

A problem of Turan. Turan observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that
\[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\]
This is probably the truth. The current best upper bound is
\[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\]
due to Razborov [Ra10].

OPEN

Let $\epsilon>0$ and $n$ be large. Let $G$ be a graph on $n$ vertices containing no $K_5$ and such that every set of $\epsilon n$ vertices contains a triangle. Must $G$ have $o(n^2)$ many edges?

The best known result is that $G$ can have at most $(\tfrac{1}{12}+o(1))n^2$ many edges.

OPEN

Show that
\[R(3,k+1)-R(3,k)\to\infty\]
as $k\to \infty$. Similarly, prove or disprove that
\[R(3,k+1)-R(3,k)=o(k).\]

See also [165] and the entry in the graphs problem collection.

OPEN

Show that if $G$ has $\binom{n}{2}$ edges then
\[R(G) \leq R(n).\]
More generally, if $G$ has $\binom{n}{2}+t$ edges with $t\leq n$ then
\[R(G)\leq R(H)\]
where $H$ is the graph formed by connected a new vertex to $t$ of the vertices of $K_n$.

In other words, are cliques extremal for Ramsey numbers. Asked by Erdős and Graham.

This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.

Equality holds when $T$ is a star on $n$ vertices.

Implied by [548].

OPEN

Let $n\geq k+1$. Every graph on $n$ vertices with at least $n(k-1)/2+1$ edges contains every tree on $k+1$ vertices.

#548:

A problem of Erdős and Sós. It can be easily proved by induction that every graph on $n$ vertices with at least $n(k-1)+1$ edges contains every tree on $k+1$ vertices.

Brandt and Dobson [BrDo96] have proved this for graphs of girth at least $5$. Wang, Li, and Liu [WLL00] have proved this for graphs whose complements have girth at least $5$. Saclé and Woznik [SaWo97] have proved this for graphs which contain no cycles of length $4$. Yi and Li [YiLi04] have proved this for graphs whose complements contain no cycles of length $4$.

SOLVED

If $T$ is a tree which is a bipartite graph with $k$ vertices and $2k$ vertices in the other class then show that $R(T)=4k$.

It follows from results in [EFRS82] that $R(T)\geq 4k-1$.

This is false: Norin, Sun, and Zhao [NSZ16] have proved that if $T$ is the union of two stars on $k$ and $2k$ vertices, with an edge joining the centre of the two stars, then $R(T)\geq (4.2-o(1))k$. The best upper bound for the Ramsey number for this tree is $R(T)\leq 4.27492k+1$, obtained by Dubó and Stein [DuSt24].

OPEN

Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that
\[R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.\]

Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.

SOLVED

Prove that
\[R(C_k,K_n)=(k-1)(n-1)+1\]
for $k\geq n\geq 3$ (except when $n=k=3$).

Asked by Erdős, Faudree, Rousseau, and Schelp, who also ask for the smallest value of $k$ such that this identity holds (for fixed $n$). They also ask, for fixed $n$, what is the minimum value of $R(C_k,K_n)$?

This identity was proved for $k>n^2-2$ by Bondy and Erdős [BoEr73]. Nikiforov [Ni05] extended this to $k\geq 4n+2$.

Keevash, Long, and Skokan [KLS21] have proved this identity when $k\geq C\frac{\log n}{\log\log n}$ for some constant $C$, thus establishing the conjecture for sufficiently large $n$.

It was shown in [BEFRS89] that
\[n+\lceil\sqrt{n}\rceil+1\geq R(C_4,S_n)\geq n+\sqrt{n}-6n^{11/40}.\]
Füredi (unpublished) has shown that $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil$ for infinitely many $n$.

SOLVED

Let $R(3,3,n)$ denote the smallest integer $m$ such that if we $3$-colour the edges of $K_m$ then there is either a monochromatic triangle in one of the first two colours or a monochromatic $K_n$ in the third colour. Define $R(3,n)$ similarly but with two colours. Show that
\[\frac{R(3,3,n)}{R(3,n)}\to \infty\]
as $n\to \infty$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that
\[\lim_{k\to \infty}\frac{R(C_{2n+1};k)}{R(K_3;k)}=0\]
for any $n\geq 2$.

A problem of Erdős and Graham. The problem is open even for $n=2$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of
\[R(C_{2n};k).\]

SOLVED

Let $R(G;3)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that
\[R(C_n;3) \leq 4n-3.\]

A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that
\[R(T;k)=kn+O(1)\]
for any tree $T$ on $n$ vertices?

A problem of Erdős and Graham. Implied by [548].

OPEN

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine
\[R(K_{s,t};k)\]
where $K_{s,t}$ is the complete bipartite graph with $s$ vertices in one component and $t$ in the other.

Chung and Graham [ChGr75] prove the bounds
\[(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s.\]
For example this implies that
\[R(K_{3,3};k) \ll k^3.\]
Using Turán numbers one can show that
\[R(K_{3,3};k) \gg \frac{k^3}{(\log k)^3}.\]

SOLVED

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.

If $G$ has $n$ vertices and maximum degree $d$ then prove that \[\hat{R}(G)\ll_d n.\]

#559:

A problem of Beck and Erdős. Beck [Be83b] proved this when $G$ is a path. Friedman and Pippenger [FrPi87] proved this when $G$ is a tree. Haxell, Kohayakawa, and Luczak [HKL95] proved this when $G$ is a cycle. An alternative proof when $G$ is a cycle (with better constants) was given by Javadi, Khoeini, Omidi, and Pokrovskiy [JKOP19].

This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that \[\hat{R}(G)\gg n(\log n)^{c}\] for some absolute constant $c>0$. Tikhomirov [Ti22b] has improved this to \[\hat{R}(G)\gg n\exp(c\sqrt{\log n}).\] It is an interesting question how large $\hat{R}(G)$ can be if $G$ has maximum degree $3$. Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS11] proved an upper bound of $\leq n^{5/3+o(1)}$ and Conlon, Nenadov, and Trujić [CNT22] proved $\ll n^{8/5}$. The best known upper bound of $\leq n^{3/2+o(1)}$ is due to Draganić and Petrova [DrPe22].

OPEN

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Determine \[\hat{R}(K_{n,n}),\] where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each component.

We know that
\[\frac{1}{60}n^22^n<\hat{R}(K_{n,n})< \frac{3}{2}n^32^n.\]
The lower bound (which holds for $n\geq 6$) was proved by Erdős and Rousseau [ErRo93]. The upper bound was proved by Erdős, Faudree, Rousseau, and Schelp [EFRS78b] and Nešetřil and Rödl [NeRo78].

Conlon, Fox, and Wigderson [CFW23] have proved that, for any $s\leq t$, \[\hat{R}(K_{s,t})\gg s^{2-\frac{s}{t}}t2^s,\] and prove that when $t\gg s\log s$ we have $\hat{R}(K_{s,t})\asymp s^2t2^s$. They conjecture that this should hold for all $s\leq t$, and so in particular we should have $\hat{R}(K_{n,n})\asymp n^32^n$.

OPEN

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Let $F_1$ and $F_2$ be the union of stars. More precisely, let $F_1=\cup_{i\leq s} K_{1,n_i}$ and $F_2=\cup_{j\leq t} K_{1,m_j}$. Prove that \[\hat{R}(F_1,F_2) = \sum_{2\leq k\leq s+2}\max\{n_i+m_j-1 : i+j=k\}.\]

Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS78] proved this when all the $n_i$ are identical and all the $m_i$ are identical.

OPEN

Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergraph on $m$ vertices then there must be some monochromatic copy of the complete $r$-uniform hypergraph on $n$ vertices.

Prove that, for $r\geq 3$, \[\log_{r-1} R_r(n) \asymp_r n,\] where $\log_{r-1}$ denotes the $(r-1)$-fold iterated logarithm. That is, does $R_r(n)$ grow like \[2^{2^{\cdots n}}\] where the tower of exponentials has height $r-1$?

OPEN

Let $F(n,\alpha)$ denote the largest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lvert X\rvert}{2}$ many edges of each colour.

Prove that, for every $0\leq \alpha\leq 1/2$, \[F(n,\alpha)\sim c_\alpha\log n\] for some constant $c_\alpha$ depending only on $\alpha$.

It is easy to show that, for every $0\leq \alpha\leq 1/2$,
\[F(n,\alpha)\asymp_\alpha \log n.\]

Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.

See also [161].

OPEN - $500

Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the $3$-uniform hypergraph on $n$ vertices.

Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]

OPEN

Let $R^*(G)$ be the induced Ramsey number: the minimal $m$ such that there is a graph $H$ on $m$ vertices such that any $2$-colouring of the edges of $H$ contains an induced monochromatic copy of $G$.

Is it true that \[R^*(G) \leq 2^{O(n)}\] for any graph $G$ on $n$ vertices?

A problem of Erdős and Rödl. Even the existence of $R^*(G)$ is not obvious, but was proved independently by Deuber [De75], Erdős, Hajnal, and Pósa [EHP75], and Rödl [Ro73].

Rödl [Ro73] proved this when $G$ is bipartite. Kohayakawa, Prömel, and Rödl [KPR98] have proved that \[R^*(G) < 2^{O(n(\log n)^2)}.\] An alternative (and more explicit) proof was given by Fox and Sudakov [FoSu08]. Conlon, Fox, and Sudakov [CFS12] have improved this to \[R^*(G) < 2^{O(n\log n)}.\]

OPEN

Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then
\[R(G,H)\ll m?\]

OPEN

Let $G$ be either $Q_3$ or $K_{3,3}$ or $H_5$ (the last formed by adding two vertex-disjoint chords to $C_5$). Is it true that, if $H$ has $m$ edges and no isolated vertices, then
\[R(G,H)\ll m?\]

In other words, is $G$ Ramsey size linear? A special case of [566]. In [Er95] Erdős specifically asks about the case $G=K_{3,3}$.

The graph $H_5$ can also be described as $K_4^*$, obtained from $K_4$ by subdividing one edge. ($K_4$ itself is not Ramsey size linear, since $R(4,n)\gg n^{3-o(1)}$, see [166].) Bradać, Gishboliner, and Sudakov [BGS23] have shown that every subdivision of $K_4$ on at least $6$ vertices is Ramsey size linear, and also that $R(H_5,H) \ll m$ whenever $H$ is a bipartite graph with $m$ edges and no isolated vertices.

OPEN

Let $G$ be a graph such that $R(G,T_n)\ll n$ for any tree $T_n$ on $n$ vertices and $R(G,K_n)\ll n^2$. Is it true that, for any $H$ with $m$ edges and no isolated vertices,
\[R(G,H)\ll m?\]

In other words, is $G$ Ramsey size linear?

OPEN

Let $k\geq 1$. What is the best possible $c_k$ such that
\[R(C_{2k+1},H)\leq c_k m\]
for any graph $H$ on $m$ edges without isolated vertices?

OPEN

Show that for any rational $\alpha \in (1,2)$ there exists a bipartite graph $G$ such that
\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]
Conversely, if $G$ is bipartite then must there exist some rational $\alpha$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}?\]

A problem of Erdős and Simonovits.

It is easy to see that $\mathrm{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor$ for any $k\geq 1$ (and $n>2k+1$) (since no bipartite graph contains an odd cycle). It is also known that $\mathrm{ex}(n;C_4)\asymp n^{3/2}$.

Erdős [Er64c] and Bondy and Simonovits [BoSi74] showed that \[\mathrm{ex}(n;C_{2k})\ll kn^{1+\frac{1}{k}}.\]

Benson [Be66] has proved this conjecture for $k=3$ and $k=5$. Lazebnik, Ustimenko, and Woldar [LUW95] have shown that, for arbitrary $k\geq 3$, \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}},\] where $\nu=0$ if $k$ is odd and $\nu=1$ if $k$ is even. See [LUW99] for further history and references.

A problem of Erdős and Simonovits, who proved that
\[\mathrm{ex}(n;\{C_4,C_5\})=(n/2)^{3/2}+O(n).\]

See also [574] and the entry in the graphs problem collection.

OPEN

Is it true that, for $k\geq 2$,
\[\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))(n/2)^{1+\frac{1}{k}}.\]

A problem of Erdős and Simonovits.

See also [573] and the entry in the graphs problem collection.

OPEN

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$. Note that it is trivial that $\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G)$ for every $G\in\mathcal{F}$.

Is it true that, for every $\mathcal{F}$, if there is a bipartite graph in $\mathcal{F}$ then there exists some bipartite $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]

A problem of Erdős and Simonovits.

See also [180] and the entry in the graphs problem collection.

OPEN

Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of
\[\mathrm{ex}(n;Q_k).\]

Erdős and Simonovits [ErSi70] proved that
\[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\]
A theorem of Sudakov and Tomon [SuTo22] implies
\[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\]
Janzer and Sudakov [JaSu22b] have improved this to
\[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\]
See also the entry in the graphs problem collection.

SOLVED

If $G$ is a random graph on $2^d$ vertices, including each edge with probability $1/2$, then $G$ almost surely contains a copy of $Q_d$ (the $d$-dimensional hypercube with $2^d$ vertices and $d2^{d-1}$ many edges).

A conjecture of Erdős and Bollobás. Solved by Riordan [Ri00], who in fact proved this with any edge-probability $>1/4$, and proves that the number of copies of $Q_d$ is normally distributed.

OPEN

Let $\epsilon>0$ and $n$ be sufficiently large. Show that, if $G$ is a graph on $n$ vertices which does not contain $K_{2,2,2}$ and $G$ has at least $\epsilon n^2$ many edges, then $G$ contains an independent set on $\gg_\epsilon n$ many vertices.

A problem of Erdős, Hajnal, Sós, and Szemerédi.

OPEN

Let $G$ be a graph on $n$ vertices such that at least $n/2$ vertices have degree at least $n/2$. Must $G$ contain every tree on at most $n/2$ vertices?

A conjecture of Erdős, Füredi, Loebl, and Sós. Ajtai, Komlós, and Szemerédi [AKS95] proved an asymptotic version, where at least $(1+\epsilon)n/2$ vertices have degree at least $(1+\epsilon)n/2$ (and $n$ is sufficiently large depending on $\epsilon$).

Komlós and Sós conjectured the generalisation that if at least $n/2$ vertices have degree at least $k$ then $G$ contains any tree with $k$ vertices.

SOLVED

Let $f(m)$ be the maximal $k$ such that a triangle-free graph on $m$ edges must contain a bipartite graph with $k$ edges. Determine $f(m)$.

Resolved by Alon [Al96], who showed that there exist constants $c_1,c_2>0$ such that
\[\frac{m}{2}+c_1m^{4/5}\leq f(m)\leq \frac{m}{2}+c_2m^{4/5}.\]

SOLVED - $100

Does there exist a graph $G$ with at most $10^{10}$ many vertices which contains no $K_4$, and yet any $2$-colouring of the edges produces a monochromatic $K_3$?

Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) Let this particular Folkman number be denoted by $N$.

Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the initial challenge of Erdős [Er75d] to beat $10^{10}$.

Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.

OPEN

Every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint paths.

A problem of Erdős and Gallai. Lovász [Lo68] proved that every graph on $n$ vertices can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint paths and cycles. Chung [Ch78] proved that every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint trees. Pyber [Py96] has shown that every connected graph on $n$ vertices can be covered by at mst $n/2+O(n^{3/4})$ paths.

Hajos [Lo68] has conjectured that if $G$ has all degrees even then $G$ can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint cycles.

See also [184] and the entry in the graphs problem collection.

OPEN

Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that

- $H_1$ has $\gg \delta^3n^2$ edges and every two edges in $H_1$ are contained in a cycle of length at most $6$, and furthermore if two edges share a vertex they are on a cycle of length $4$, and
- $H_2$ has $\gg \delta^2n^2$ edges and every two edges in $H_2$ are contained in a cycle of length at most $8$.

A problem of Erdős, Duke, and Rödl. Duke and Erdős [DuEr83], who proved the first if $n$ is sufficiently large depending on $\delta$. The real challenge is to prove this when $\delta=n^{-c}$ for some $c>0$. Duke, Erdős, and Rödl [DER84] proved the first statement with a $\delta^5$ in place of a $\delta^3$.

Fox and Sudakov [FoSu08b] have proved the second statement when $\delta >n^{-1/5}$.

OPEN

What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?

Pyber, Rödl, and Szemerédi [PRS95] constructed such a graph with $\gg n\log\log n$ edges.

Chakraborti, Janzer, Methuku, and Montgomery [CJMM24] have shown that such a graph can have at most $n(\log n)^{O(1)}$ many edges. Indeed, they prove that there exists a constant $C>0$ such that for any $k\geq 2$ there is a $c_k$ such that if a graph has $n$ vertices and at least $c_kn(\log n)^{C}$ many edges then it contains $k$ pairwise edge-disjoint cycles with the same vertex set.

OPEN

Let $G_1$ and $G_2$ be two graphs with chromatic number $\aleph_1$. Must there be a graph $H$ with chromatic number $4$ which appears as a subgraph of both $G_1$ and $G_2$? Is there such an $H$ with chromatic number $\aleph_0$?

Erdős also asks about finding a common subgraph $H$ (with chromatic number either $4$ or $\aleph_0$) in any finite collection of graphs with chromatic number $\aleph_1$.

Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős writes that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.

OPEN - $250

Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?

A problem of Erdős and Hajnal. Folkman, Nešetřil, and Rödl have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs (so Erdős writes, but I cannot find the reference).

See also [596].

OPEN

For which graphs $G_1,G_2$ is it true that

- for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet
- for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$.

Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees).

Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595].

OPEN

Let $G$ be a graph on at most $\aleph_1$ vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$ vertices in each class). Is it true that
\[\omega_1^2 \to (\omega_1\omega, G)^2?\]
What about finite $G$?

Erdős and Hajnal proved that $\omega_1^2 \to (\omega_1\omega,3)^2$. Erdős originally asked this with just the assumption that $G$ is $K_4$-free, but Baumgartner proved that $\omega_1^2 \not\to (\omega_1\omega, K_{\aleph_0,\aleph_0})^2$.

SOLVED

Let $G$ be a (possibly infinite) graph and $A,B$ be disjoint independent sets of vertices. Must there exist a family $P$ of disjoint paths between $A$ and $B$ and a set $S$ which contains exactly one vertex from each path in $P$, and such that every path between $A$ and $B$ contains at least one vertex from $S$?

Sometimes known as the Erdős-Menger conjecture. When $G$ is finite this is equivalent to Menger's theorem. Erdős was interested in the case when $G$ is infinite.

This was proved by Aharoni and Berger [AhBe09].

OPEN

Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that
\[e(n,r+1)-e(n,r)\to \infty\]
as $n\to \infty$? Is it true that
\[\frac{e(n,r+1)}{e(n,r)}\to 1\]
as $n\to \infty$?

OPEN

For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\alpha$?

A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

OPEN

Let $G$ be a graph with $n$ vertices and at least $n^2/4$ edges. Are there at least $2n^2/9$ edges of $G$ which are contained in a $C_5$?

Erdős [Er97d] stated that, under the same assumptions, there at least $2n^2/9$ edges of $G$ which are contained in some odd cycle. He wrote that a positive answer to this question would follow if we knew that $G$ must contain a triangle such that there at least $n/2-O(1)$ vertices joined to at least two vertices of the triangle.

Erdős and Faudree observed that every graph with $2n$ vertices and at least $n^2+1$ edges has a triangle whose vertices are joined to at least $n+2$ vertices.

SOLVED

Let $f(n)$ be minimal such that if the edges of $K_{2^n+1}$ are coloured with $n$ colours then there must be a monochromatic odd cycle of length at most $m$. Estimate $f(n)$. Does $f(n)\to \infty$ as $n\to \infty$?

A problem of Erdős and Graham. The edges of $K_{2^n}$ can be $n$-coloured to avoid odd cycles of any length. It can be shown that $C_5$ and $C_7$ can be avoided for large $n$.

Day and Johnson [DaJo17] have shown that \[f(n)\geq 2^{c\sqrt{\log n}}\] for some constant $c>0$.

OPEN

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the clique transversal number).

Estimate $\tau(G)$. In particular, is it true that if $G$ has $n$ vertices then \[\tau(G) \leq n-c\sqrt{n\log n}\] for some absolute constant $c>0$?

A problem of Erdős, Gallai, and Tuza, who proved that
\[\tau(G) \leq n-\sqrt{2n}+O(1).\]

This would be best possible, since there exist triangle-free graphs with all independent sets of size $O(\sqrt{n\log n})$, which follows from the lower bound for $R(3,k)$ by Kim [Ki95] (see [165]).

Indeed, Erdős, Gallai, and Tuza speculate that if $f(n)$ is the largest $k$ such that every triangle-free graph on $n$ vertices contains an independent set on $f(n)$ vertices, then $\tau(G)\leq n-f(n)$.

In [Er94] and [Er99] Erdős asks for a weaker upper bound $\tau(G) \leq n-\omega(n)\sqrt{n}$ for any $\omega(n)\to \infty$.

See also [611], this entry and and this entry in the graphs problem collection.

OPEN

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the clique transversal number).

Is it true that if all maximal cliques in $G$ have at least $cn$ vertices then $\tau(G)=o_c(n)$?

Similarly, estimate for $c>0$ the minimal $k_c(n)$ such that if every maximal clique in $G$ has at least $k_c(n)$ vertices then $\tau(G)<(1-c)n$.

A problem of Erdős, Gallai, and Tuza [EGT92], who proved for the latter question that $k_c(n) \geq n^{c'/\log\log n}$ for some $c'>0$, and that if every clique has size least $k$ then $\tau(G) \leq n-(kn)^{1/2}$. Bollobás and Erdős proved that if every maximal clique has at least $n+3-2\sqrt{n}$ vertices then $\tau(G)=1$ (and this threshold is best possible).

See also [610] and the entry in the graphs problem collection.

OPEN

Let $G$ be a connected graph with $n$ vertices, minimal degree $d$, and diameter $D$. Show if that $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ then
\[D\leq \frac{2(r-1)(3r+2)}{(2r^2-1)d}n+O(1),\]
and if $G$ contains no $K_{2r+1}$ and $3r-1 \mid d$ then
\[D\leq \frac{3r-1}{rd}n+O(1).\]

A problem of Erdős, Pach, Pollack, and Tuza.

OPEN

Let $n\geq 3$ and $G$ be a graph with $\geq 2n+1$ vertices and $\binom{2n+1}{2}-\binom{n}{2}-1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$?

Faudree proved that this is true if $G$ has $2n+1$ vertices.

OPEN

Let $f(n,k)$ be minimal such that there is a graph with $n$ vertices and $f(n,k)$ edges where every set of $k+2$ vertices induces a subgraph with maximum degree at least $k$. Determine $f(n,k)$.

SOLVED

Does there exist some constant $c>0$ such that if $G$ is a graph with $n$ vertices and $\geq (1/8-c)n^2$ edges then $G$ must contain either a $K_4$ or an independent set on at least $n/\log n$ vertices?

A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS93]. In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that
\[\mathrm{rt}(n; 4,n/\log n)< (1/8-c)n^2?\]
Erdős, Hajnal, Sós, and Szemerédi [EHSS83] proved that for any fixed $\epsilon>0$
\[\mathrm{rt}(n; 4,\epsilon n)< (1/8+o(1))n^2.\]
Sudakov [Su03] proved that
\[\mathrm{rt}(n; 4,ne^{-f(n)})=o(n^2)\]
whenever $f(n)/\sqrt{\log n}\to \infty$.

Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that \[\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2\] whenever $f(n) =o(\sqrt{\log n/\log\log n})$.

See also [22] and the entry in the graphs problem collection.

OPEN

Let $r\geq 3$. For an $r$-uniform hypergraph $G$ let $\tau(G)$ denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in $G$.

Determine the best possible $t$ such that, if $G$ is an $r$-uniform hypergraph $G$ where every subgraph $G'$ on at most $3r-3$ vertices has $\tau(G')\leq 1$, we have $\tau(G)\leq t$.

Erdős, Hajnal, and Tuza [EHT91] proved that this $t$ satisfies
\[\frac{3}{16}r+\frac{7}{8}\leq t \leq \frac{1}{5}r.\]

OPEN

Let $r\geq 3$. If the edges of $K_{r^2+1}$ are $r$-coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$.

In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99], who proved it for $r=3$ and $r=4$ (and observered it is false for $r=2$), and showed this property fails for infinitely many $r$ if we replace $r^2+1$ by $r^2$.

OPEN

For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$?

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$.

Erdős, Gyárfás, and Ruszinkó [EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.

See also [619].

OPEN

For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$.

Is it true that there exists a constant $c>0$ such that if $G$ is connected then $h_4(G)<(1-c)n$?

OPEN

If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?

OPEN

Let $G$ be a graph on $n$ vertices, $\alpha_1(G)$ be the maximum number of edges that contain at most one edge from every triangle, and $\tau_1(G)$ be the minimum number of edges that contain at least one edge from every triangle.

Is it true that \[\alpha_1(G)+\tau_1(G) \leq \frac{n^2}{4}?\]

A problem of Erdős, Gallai, and Tuza [EGT96], who observe that this is probably quite difficult since there are different examples where equality hold: the complete graph, the complete bipartite graph, and the graph obtained from $K_{m,m}$ by adding one vertex joined to every other.

OPEN

Let $G$ be a regular graph with $2n$ vertices and degree $n+1$. Must $G$ have $\gg 2^{2n}$ subsets that are on a cycle?

A problem of Erdős and Faudree. Erdős writes 'it is easy to see' that there are at least $(\frac{1}{2}+o(1))2^{2n}$ sets that are not on a cycle. If the regularity condition is replaced by minimum degree $n+1$ then the answer is no.

OPEN - $1000

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. Let $\chi(G)$ denote the chromatic number.

If $G$ is a random graph with $n$ vertices and each edge included independently with probability $1/2$ then is it true that almost surely \[\chi(G) - \zeta(G) \to \infty\] as $n\to \infty$?

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).

OPEN

Let $k\geq 4$ and $g_k(n)$ denote the largest $m$ such that there is a graph on $n$ vertices with chromatic number $k$ and girth $m$. Does
\[\lim_{n\to \infty}\frac{g_k(n)}{\log n}\]
exist?

OPEN

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
\[\lim_{n\to\infty}\frac{f(n)}{n/(\log n)^2}\]
exist?

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].\]

OPEN

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?

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$.

OPEN

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 colour on its list can be chosen such that adjacent vertices receive distinct colours.

Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$.

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 with property B (i.e. there is a set which intersects each member of the member yet does not contain any of them) then $m(k)\leq n(k)\leq m(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.\]

SOLVED

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 colour on its list can be chosen such that adjacent vertices receive distinct colours.

Does every planar bipartite graph $G$ have $\chi_L(G)\leq 3$?

SOLVED

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 colour on its list can be chosen such that adjacent vertices receive distinct colours.

Does every planar graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?

OPEN

A graph is $(a,b)$-choosable if for any assignment of a list of $a$ colours to each of its vertices there is a subset of $b$ colours from each list such that the subsets of adjacent vertices are disjoint.

If $G$ is $(a,b)$-choosable then $G$ is $(am,bm)$-choosable for every integer $m\geq 1$.

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$.