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.

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.

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

See also the entry in the graphs problem collection.

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

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

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

Alon has observed this problem is essentially identical to [134], and his solution in this note also solves this problem in the affirmative.

See also [619].

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98] who proved that $h_3(G)\leq n$ and $h_5(G) \leq \frac{n-1}{2}$ and there exist connected graphs $G$ on $n$ vertices with $h_3(G)\geq n-c$ for some constant $c>0$.

If we omit the condition that the graph must remain triangle-free then Alon, Gyárfás, and Ruszinkó [AGR00] have proved that adding $n/2$ edges always suffices to obtain diameter at most $4$.

See also [134] and [618].

This was first asked by Erdős and Rogers [ErRo62], and is generally known as the Erdős-Rogers problem. Let $f(n)$ be such that every such graph contains a triangle-free subgraph with at least $f(n)$ vertices.

It is now known that $f(n)=n^{1/2+o(1)}$. Bollobás and Hind [BoHi91] proved \[n^{1/2} \ll f(n) \ll n^{7/10+o(1)}.\] Krivelevich [Kr94] improved this to \[n^{1/2}(\log\log n)^{1/2} \ll f(n) \ll n^{2/3}(\log n)^{1/3}.\] Wolfovitz [Wo13] proved \[f(n) \ll n^{1/2}(\log n)^{120}.\]

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.

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.

A problem of Erdős and Hajnal [ErHa58], who proved that if $\lvert X\rvert <\aleph_\omega$ then the answer is no. Erdős suggests in [Er99] that this problem is 'perhaps undecidable'.

A problem of Erdős and Hajnal [ErHa68] who proved that \[\log_2 n \leq H(n) < \log_2n +(3+o(1))\log_2\log_2n.\] Erdős said that even the weaker statement that for $n=2^k$ we have $H(n)\geq k+1$ is open, but Alon has provided the following simple proof: by the pigeonhole principle there are $\frac{n-1}{2}$ subsets $A_i$ of size $2$ such that $f(A_i)$ is the same. Any set $Y$ of size $k$ containing at least $k/2$ of them can have at most \[2^k-\lfloor k/2\rfloor+1< 2^k=n\] distinct elements in the union of the images of $f(A)$ for $A\subseteq Y$.

For this weaker statement, Erdős and Gyárfás conjectured the stronger form that if $\lvert X\rvert=2^k$ then, for any $f:\{A : A\subseteq X\}\to X$, there must exist some $Y\subset X$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}< 2^k-k^C\] for every $C$ (with $k$ sufficiently large depending on $C$). This was proved by Alon (personal communication), who proved the stronger version that, for any $\epsilon>0$, if $k$ is large enough, there must exist some $Y$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}<(1-\epsilon)2^k.\] Alon also proved that, provided $k$ is large enough, if $\lvert X\rvert=2^k$ there exists some $f:\{A: A\subseteq X\}\to X$ such that, if $Y\subset X$ with $\lvert Y\rvert=k$, then \[\#\{ f(A) : A\subseteq Y\}>\tfrac{1}{4}2^k.\]