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

Updated Oct 8

Problem 595

claims/: The 1 claim page of Problem 595, one per claimant's result; the problem's standing derives from them.

Statement. Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?

Status. Open. The site labels Problem 595 OPEN. The one claim recorded here is imported from the site's ruling on the identical first question of Problem 1174, which it labels NOT DISPROVABLE, crediting Shelah; the claim page Shelah 1989 records that result, which is one side of an independence result, so the problem is open on it.

Source. erdosproblems.com/595, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #595, https://www.erdosproblems.com/595.

References.

[Fo70] Folkman, Jon, Graphs with monochromatic complete subgraphs in every edge coloring. SIAM J. Appl. Math. (1970), 19-24.
[NeRo75] Nešetřil, Jaroslav and Rödl, Vojtěch, Type theory of partition properties of graphs. (1975), 405-412.

Formalization. Statement in formal-conjectures.

Current assessment

The site labels the problem OPEN and its remarks record only the finite analog: Folkman [Fo70] for two colors and Nešetřil and Rödl [NeRo75] for every $n$ proved that there is a $K_4$ -free graph that is not the union of $n$ triangle-free graphs, which is Folkman's Theorem 1 with $k_1=k_2=3$ (result page theorem_1) and its extension to every number of colors. The question itself, whether one $K_4$ -free graph defeats countably many colors, has a consistent positive answer: Shelah (Lecture Notes in Math. 1401, 1989, Lemma 5.1 with $k(*)=3$ and $\mu=\aleph_0$ ) proved by forcing, from a measurable cardinal or one of the lemma's weaker hypotheses, that such a graph can exist, so relative to that hypothesis ZFC cannot refute a positive answer; this is the accepted partial claim on Shelah 1989, with the value not_disprovable that the site gives the identical first question of Problem 1174. It is one side of an independence result, so the problem stays open. Komjáth's survey (Bull. Symbolic Logic 31 (2025), Problem 53) records Shelah's consistency proof and records that existence in ZFC is open, which is the open part of the problem: a ZFC construction would answer the question outright, and a proof that no such graph exists would contradict Shelah's result and so would need the lemma's hypothesis to be inconsistent. Any such graph has more than $2^{\aleph_0}$ vertices, as the Known Results explain. No formal proof is recorded: the formal-conjectures statement file, as of 2026-10-07, marks only the finite analog research solved, and the community database lists the problem as open.

Known Results

The question is the first question of Problem 1174 in other words, and Komjáth's survey notes the same cardinality obstruction: the required graph has more than $2^{\aleph_0}$ vertices, since the complete graph on $2^{\aleph_0}$ vertices is a countable union of bipartite graphs.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (23)

Problem 924 Shelah's consistent K_4-free graph that is no countable union of triangle-free graphs problems/set_theory/E0595/claims Problem 596 The pair (C_4, C_6) has the finite-versus-countable Ramsey gap Problem 1174 Shelah's consistent K_4-free graph forcing a monochromatic triangle Set Theory and Infinite Combinatorics set_theory/erdos_1967_decomposition_graphs Definitions 1.1, 2.1, 2.2 and 6.1: decompositions, the clique bound beta(G), the decomposition symbols and the colouring number 2.7 (p. 361): every graph on 2^gamma vertices is an edge-union of gamma triangle-free graphs Section 5, display (1) (p. 370): the conjectured best negative edge-decomposition relation, with Problems 2 and 3 and the finite case of Section 6 Theorem 1 (p. 362): [alpha, delta+1] does not arrow [gamma, delta] for infinite alpha and gamma < alpha Theorem 6 (p. 369): a graph with beta(G) = beta+1 omitting K_{beta+1} minus an edge splits into countably many K_beta-free classes Theorem 7 (p. 370): (alpha, omega) does not arrow (gamma, delta) for alpha = (2^{(2^gamma)^+})^+ and every finite delta set_theory/erdos_1987_problems_finite_infinite_graphs Problem 5 (pp. 224–225): a K₄-free graph that is not a countable union of triangle-free graphs set_theory/folkman_1970_graphs_monochromatic_complete_subgraphs_every_edge set_theory/komjath_2025_erdos_hajnal_problem_list set_theory/shelah_1989_consistency_positive_partition_theorems_graphs_models Conclusion 1.6 (p. 175): from a class of measurables, a forcing extension where every model has a partition-arrow host Conclusion 4.2 (p. 187): the positive partition theorem for models without measurable cardinals Lemma 5.1 (p. 188): a forcing that adds a K_{k(*)+1}-free graph G with G -> (K_{k(*)})^2_mu

Graph