---

Claim. Let $f(k_1,k_2)$ be the least clique number of a finite graph in which every partition of the edges into two classes has $k_1$ mutually adjacent vertices joined within the first class or $k_2$ within the second. Folkman's Theorem 1 states that $f(k_1,k_2)=\max(k_1,k_2)$ for all $k_1,k_2\ge2$. With $k_1=k_2=l$ there is a graph of clique number $l$, so with no $K_{l+1}$, in which every $2$-coloring of the edges contains a monochromatic $K_l$: the case $k=2$ of Problem 924 for every $l\ge3$. The theorem is paged at Theorem 1 of the library's source card. The proof (pp. 21--23) is an induction on $k_1+k_2$ that builds the graph by a product construction from the vertex-partition graphs of the paper's Theorem 2.

Covers. The case $k=2$ for every $l\ge3$. For $k\ge3$ the paper's closing Remarks (pp. 23--24) define the $n$-class function $f(k_1,\ldots,k_n)$, conjecture that it equals $\max(k_1,\ldots,k_n)$ and say that the methods of the paper do not seem to extend beyond two classes; the bound asserted there, with no proof printed, $f(k_1,\ldots,k_n)\le k_1+\min(\tfrac12\sum_{i\ge2}(k_i-2),\sum_{i\ge3}(k_i-2))$ for $k_1\ge\dots\ge k_n\ge2$, gives for $l=3$ and three colors only a $K_5$-free graph. The general case is the accepted claim Nešetřil and Rödl 1976.

Depends on. Nothing in this wiki; the result rests on the cited paper alone.

Acceptance. Refereed: J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970), no. 1, 19--24 (the publisher's record places the article in the January 1970 issue). Reviewed: the site's curator, T. F. Bloom, credits the theorem with the case $k=2$ in the problem's commentary, on a page the site labels PROVED, and Spencer's refereed 1975 paper (J. Combin. Theory Ser. A 19 (1975), 278--286) cites it for the case $l=3$ in its introduction. Semantic Scholar's citation list (the first hundred records, scanned by title,) records no dispute.

Dating. The page is dated by the issue month, January 1970; the day is a placeholder, since the publisher's record gives none. The paper was received on 30 November 1967 and presented at a symposium that year.

Read depth. The page rests on the definitions (p. 19), Theorem 1 (p. 20) and the Remarks (pp. 23--24), and on the structure of the proof (pp. 21--23); no step of the proof is checked, so nothing is independently reviewed in this corpus.