---

Statement

$K(\ell)$ is the complete graph on $\ell$ vertices (the paper's notation).

Conjecture (Erdős and Hajnal; p. 184, quoted). "Hajnal and I conjectured that for every $k$ and $\ell\ge3$ there is a $G_{k,\ell}$ which contains no $K(\ell+1)$ but if one colors the edges of $G_{k,\ell}$ by $k$ colors in an arbitrary way there always is a monochromatic $K(\ell)$."

What the paper reports (p. 184). Folkman (the paper's reference [11]) proved the conjecture for $k=2$, and Nešetřil and Rödl proved the general conjecture, in fact a much more general theorem; no reference is given for the second result. The graphs are finite: the next page defines the least number of vertices of such a graph (see the problem of p. 185).

Source. P. Erdős, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 183--192; Section III, p. 184. The edition read is identified on the source card. Reference [11] is J. Folkman, Graphs with monochromatic complete subgraphs in every edge-colouring, SIAM J. Appl. Math. 18 (1970), 19--24.

Read depth. Claims checked: the paragraph was read clause by clause on the printed page. The paper gives no proofs.

Proof pointer

None in this paper; Folkman's result is reported with reference [11], that of Nešetřil and Rödl without a reference.

Dependencies

None within the paper.

Bears on

• Problem 582: the problem asks for a $K_4$-free graph in which every $2$-coloring of the edges has a monochromatic triangle, which is the case $k=2$, $\ell=3$ of the conjecture, a case the paper reports Folkman proved.