Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman has proved the conjecture for $n<10$. 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.
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.
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].
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]).
In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]
What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_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].
How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?
See also [213].
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$?
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}.\]
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].\]
Balogh, Kostochka, Prince, and Stiebitz [BKPS09] have proved the full conjecture for quasi-line graphs and graphs with independence number $2$.
Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>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.\]
Does every planar bipartite graph $G$ have $\chi_L(G)\leq 3$?
Does every planar graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?
If $G$ is $(a,b)$-choosable then $G$ is $(am,bm)$-choosable for every integer $m\geq 1$.
This is false: Dvořák, Hu, and Sereni [DHS19] construct a graph which is $(4,1)$-choosable but not $(8,2)$-choosable.
Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does \[\lim_{n\to \infty}\chi(G_n)^{1/n}\] exist?
Is there some $k$ such that if $G$ has girth $\geq k$ (i.e. $G$ contains no cycles of length $<k$) then $\chi(G)\leq 3$?
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.
Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?
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$.
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$).
Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?
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$).
See also [75].
Does there exist some constant $c>0$ such that \[\chi_L(G)+\chi_L(G^c)> n^{1/2+c}\] for every graph $G$ on $n$ vertices (where $G^c$ is the complement of $G$)?
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.
Determine $z(n)$ for small values of $z(n)$. In particular is it true that $z(12)=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}$.
Let $z(S_n)$ be the maximum value of $\zeta(G)$ over all graphs $G$ which can be embedded on $S_n$, the orientable surface of genus $n$. Determine the growth rate of $z(S_n)$.
If $G$ is a graph with chromatic number $\chi(G)=m$ then must $G$ contain a subgraph $H$ with \[\zeta(H) \gg \frac{m}{\log m}?\]
The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].
Must a graph with large chromatic number have large dichromatic number? Must a graph with large cochromatic number contain a graph with large dichromatic number?
Is it true that if $G$ has no $K_5$ and $\zeta(G)\geq 4$ then $\chi(G) \leq \zeta(G)+2$?
This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.
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].
Estimate $f(d)$. In particular is it true that $f(d)=o(d^2)$?
Resolved by Alon, McDiarmid, and Reed [AMR91] who showed \[\frac{d^{4/3}}{(\log d)^{1/3}}\ll f(d) \ll d^{4/3}.\]
Is it true that $\chi_L(G)=o(n)$ for almost all graphs on $n$ vertices?
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.
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$.
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.
Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.
