Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. For every finite graph GG and every number cc of colors there is a finite graph HH with H→(G)cH\to(G)_c and ω(H)=ω(G)\omega(H)=\omega(G): every cc-coloring of the edges of HH contains a monochromatic copy of GG, and the clique number of HH equals that of GG. With G=KlG=K_l and c=kc=k the graph HH has clique number ll, so it contains no Kl+1K_{l+1}, and every kk-coloring of its edges has a monochromatic KlK_l; this is the statement of Problem 924 for every k≥2k\ge2 and l≥3l\ge3, so the answer is yes. The two-color case had been proved by Folkman, whose paper states the general case as a conjecture beyond its methods; it is the accepted partial claim Folkman 1970.

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

Acceptance. Refereed: J. Nešetřil and V. Rödl, The Ramsey property for graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20 (1976), no. 3, 243--249 (the publisher's record dates the issue June 1976, which this page is named by; the day is a placeholder). Reviewed: the site's curator, T. F. Bloom, credits the theorem with the general case in the problem's commentary, on a page the site labels PROVED; Spencer's refereed 1975 paper states it in its introduction (printed p. 278) as the full generalization of Folkman's theorem, and Erdős's 1975 report credits Nešetřil and Rödl with the answer for every number of colors, their paper then unpublished. Semantic Scholar's citation list (the first hundred records, 1986 to 2026, scanned by title,) records no dispute.

Read depth. The paper is not held; no open copy was found on 2026-09-18. The statement above is quoted second-hand from Spencer's introduction (printed p. 278; the library's source card), from Erdős's 1975 report (printed p. 306) and from the site. Reopening condition: a copy of the paper read at its main theorem.