Asks whether every graph whose subgraphs on $k\ge2$ vertices have at most $2k-3$ edges is Ramsey size linear; open. This corrects the erdosproblems.com wording, which no graph meets, since a one-vertex subgraph exceeds the bound.

• Graph theory
• Ramsey theory

Asks whether each of the cube $Q_3$, the graph $K_{3,3}$ and the graph $H_5$ ($K_4$ with one edge subdivided) is Ramsey size linear; open, with partial results.

• Graph theory
• Ramsey theory

Asks whether every graph $G$ with $R(G,T_n)\ll n$ for all trees $T_n$ on $n$ vertices and $R(G,K_n)\ll n^2$ satisfies $R(G,H)\ll m$ for every graph $H$ with $m$ edges and no isolated vertices.

• Graph theory
• Ramsey theory

Asks whether $\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}$ for every $k\ge3$, that is, whether some $C_{2k}$-free graph on $n$ vertices has that many edges. It is known for $k=3$ and $k=5$ and open for every other $k$.

• Graph theory
• Turán numbers
• Cycles

Asks whether $\mathrm{ex}(n;\{C_3,C_4\})$, the most edges of a graph on $n$ vertices with no triangle and no four-cycle, is asymptotic to $(n/2)^{3/2}$. The ratio is known only to lie between $1$ and $\sqrt2$.

• Graph theory
• Turán numbers

Asks for the behaviour of $\mathrm{ex}(n;Q_k)$, the most edges of a graph on $n$ vertices with no $k$-dimensional hypercube $Q_k$. For the cube the order lies between $n^{3/2}$ and $n^{8/5}$, which refutes Erdős's first guess.

• Graph theory
• Turán numbers

Asks whether every graph on $n$ vertices in which at least $n/2$ vertices have degree at least $n/2$ contains every tree on at most $n/2$ vertices. Zhao proved it for large $n$, and finitely many orders remain unchecked.

• Graph theory

Asks whether every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint paths (Gallai's path decomposition conjecture). It is proved for several classes and open in general.

• Graph theory

Asks whether every graph on $n$ vertices with $\delta n^2$ edges, where $\delta$ may shrink as a power of $n$, contains dense subgraphs in which any two edges lie together on a short cycle.

• Graph theory
• Cycles

Asks for the maximum number of edges in a graph on $n$ vertices with no two edge-disjoint cycles on the same vertex set. The maximum is known to be $\Omega(n\log\log n)$ and $O(n(\log n)^t)$ for some constant $t$.

• Graph theory
• Cycles

Asks whether, for $k\ge4$, $n$ points in the plane with no $k+1$ on a line determine only $o(n^2)$ lines through $k$ points.

• Geometry

Asks to estimate $g(n)$, the size of the largest subset with no three points on a line that can always be found among $n$ points in the plane with no four on a line.

• Geometry

Asks which countable ordinals $\beta$ make every red-blue coloring of the pairs from $\omega^\beta$ give a red complete subgraph of order type $\omega^\beta$ or a blue triangle.

• Set theory
• Ramsey theory

Asks whether there is an infinite $K_4$-free graph that is not a union of countably many triangle-free graphs.

• Graph theory
• Set theory

Asks for which graphs $G_1,G_2$ every finite number of colors forces a monochromatic $G_2$ in some $G_1$-free graph, while countably many colors never do. Erdős and Hajnal first guessed that no pair exists, which $C_4$ and $C_6$ refute.

• Graph theory
• Ramsey theory
• Set theory

Asks whether $\omega_1^2\to(\omega_1\omega,G)^2$ holds for every graph $G$ on at most $\aleph_1$ vertices with no $K_4$ and no $K_{\aleph_0,\aleph_0}$. Erdős first asked it for every $K_4$-free graph, which a relation of Baumgartner refutes.

• Graph theory
• Ramsey theory
• Set theory

Asks whether the countable subsets of an infinite cardinal $m$ can be colored with $\kappa=(2^{\aleph_0})^+$ colors so that every subset of $m$ of size $\kappa$ contains sets of every color.

• Set theory
• Ramsey theory

Let $e(n,r)$ be the least number of edges that forces an edge in at least $r$ triangles in an $n$-vertex graph where every edge lies in a triangle. Asks whether $e(n,r+1)-e(n,r)\to\infty$ and $e(n,r+1)/e(n,r)\to1$.

• Graph theory

Asks for which limit ordinals $\alpha$ every graph on vertex set $\alpha$ has an infinite path or an independent set of order type $\alpha$.

• Graph theory
• Set theory

Asks whether every family of countably infinite sets, any two meeting in a finite set of size other than $1$, has a $2$-coloring of its union with no set monochromatic.

• Combinatorics
• Set theory

Asks whether any $n$ distinct points in the plane must include a point with $\gg n^{1-o(1)}$ distinct distances to the others.

• Geometry
• Distances

Asks for estimates of the least $m$ such that every $n$-coloring of the edges of $K_{2^n+1}$ has a monochromatic odd cycle of length at most $m$.

• Graph theory
• Ramsey theory

Asks whether cliques of at least $cn$ vertices force a sublinear clique transversal $\tau$, and which clique size $k_c(n)$ forces $\tau<(1-c)n$. Open; by 1992, $k_c(n)\ge n^{c'/\log\log n}$ for infinitely many $n$, and $\tau\le n-\sqrt{kn}$ with small exceptions if cliques exceed $k$ vertices.

• Graph theory

Asks for the fewest edges in a graph on $n$ vertices in which every set of $k+2$ vertices induces a subgraph of maximum degree at least $k$.

• Graph theory

Asks for the best bound $t$ on the covering number of an $r$-uniform hypergraph, $r\ge3$, in which every subhypergraph on at most $3r-3$ vertices has covering number at most $1$.

• Graph theory