4 solved out of 18 shown (show only solved or open)
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 Erdős and Hajnal, and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density. 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.

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
Does every infinite graph with infinite chromatic number contain a cycle of length $2^n$ for infinitely many $n$?
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).
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$. Additional thanks to: Yuval Wigderson 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 it true that $\sum\frac{1}{a_i}\gg \log k?$ 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$. See also [57]. SOLVED Is it true that for every infinite arithmetic progression$P$which contains even numbers there is some constant$c=c(P)$such that every graph with average degree at least$c$contains a cycle whose length is in$P$? This has been proved by Bollobás [Bo77]. The best dependence of the constant$c(P)$is unknown. See also [72]. 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 [Bo77] proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers (see [71]).

Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although he conjectured 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.

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? 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]). OPEN 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)$. Prove that$f(n)/2^{n/2}\to \infty$. Conjectured by Erdős and Faudree, who showed that$2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte [Ve04], who proved $f(n)\ll 2^{n-n^c}$ for some constant$c>0$. One can also ask about the existence and value of$\lim f(n)^{1/n}$. Additional thanks to: Tuan Tran 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 Any graph on$n$vertices can be decomposed into$O(n)$many cycles and edges. Conjectured by Erdős and Gallai, who proved that$O(n\log n)$many cycles and edges suffices. The best bound available is due to Bucić and Montgomery [BM22], who prove that$O(n\log^*n)$many cycles and edges suffice, where$\log^*$is the iterated logarithm function. See also [583]. 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$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? It is known that $\frac{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]. OPEN Is there some constant$C$such that any graph$G$on$n$vertices with$\geq Cn$edges must contain a cycle which has at least as many diagonals as vertices? A problem of Hamburger and Szegedy. OPEN Let$G$be a graph with minimum degree$k$and girth$>2s$(i.e.$G$contains no cycles of length$\leq 2s$). Must there be$\gg k^s$many distinct cycle lengths in$G$? A question of Erdős, Faudree, and Schelp, who proved it when$s=2\$.