---

Claim. Problem 595 asks for an infinite graph $G$ with no $K_4$ that is not the union of countably many triangle-free graphs. A graph is a countable union of triangle-free graphs exactly when its edges have a coloring with countably many colors and no monochromatic triangle, so the question asks for a $K_4$-free graph $G$ with $G\to(K_3)^2_{\aleph_0}$; such a graph is automatically infinite, since a finite graph is a countable union of single edges. Section 5 of Shelah's chapter addresses this question, which it calls an old one of Erdős and Hajnal, and proves the consistency of a slightly stronger statement. Lemma 5.1: if $\mu<\lambda<\kappa$, $\kappa$ is a measurable cardinal (or one of two weaker hypotheses the lemma states holds, one on $\kappa$ and one on $\lambda$, in the chapter's notation), $2\le m<\omega_1$ and $\lambda=\lambda^{<\lambda}$, then some $\lambda^+$-c.c., $\lambda$-complete forcing notion of power $\kappa$ forces $2^\lambda=\kappa$ and adds a graph $G$ of power $\kappa$ with $G\to(K_{k(*)})^2_\mu$ that embeds no $K_{k(*)+1}$. With $k(*)=3$ and $\mu=\aleph_0$ the extension has a $K_4$-free graph of power $2^\lambda$ that is not a countable union of triangle-free graphs. So, relative to the consistency of ZFC with the lemma's hypothesis, ZFC does not refute a positive answer: the question is not disprovable in the site's sense. Existence of such a graph in ZFC is open, as Komjáth's 2025 survey records (Problem 53), and any such graph has more than $2^{\aleph_0}$ vertices, since the complete graph on $2^{\aleph_0}$ vertices is a countable union of bipartite graphs. The same result is recorded for the identical first question of Problem 1174 on the E1174 claim page.

Covers. One side of an independence result: relative to the lemma's hypothesis, ZFC does not refute the existence of such a graph. It does not show that ZFC cannot prove the existence of one, and it gives no ZFC construction, so it leaves Problem 595 open.

Source. Saharon Shelah, Consistency of positive partition theorems for graphs and models, in Set theory and its applications (Toronto, ON, 1987), J. Steprāns, ed., Lecture Notes in Mathematics 1401, Springer, Berlin, 1989, pp. 167–193; DOI 10.1007/BFb0097339; Shelah archive Sh:289, whose copy the archive labels the published version and which is the second link above. The source card records the chapter's results and calls this problem's question the one its Section 5 answers consistently. The volume carries only the year, so this page is dated the first of January 1989.

Acceptance. Reviewed: Péter Komjáth's survey, The Erdős–Hajnal problem list, Bull. Symbolic Logic 31 (2025), 418–461, DOI 10.1017/bsl.2025.1, records at its Problem 53 that Shelah proved the consistency of a $K_4$-free graph every countable edge coloring of which has a monochromatic triangle, and records that existence in ZFC is open; the survey is refereed, and its author is independent of Shelah. The site labels Problem 595 OPEN and its remarks do not credit Shelah; the curator's label NOT DISPROVABLE and credit to Shelah under Problem 1174, the same question in other words, is disclosed and not counted here. The chapter appeared in a Springer Lecture Notes in Mathematics proceedings volume, and no evidence that the volume's chapters were refereed is recorded, so refereed is not listed. Nothing on this page is independently reviewed by this project.

Depends on. No other wiki page; the claim rests on the chapter above.