Unions of triangle free graphs

Authors: Erdos, Paul, Hajnal, Andras— posted by mdevos on 2007-06-04

Status open low confidence

The problem asks whether, provably in ZFC, there exists a $K_4$-free graph whose edge set cannot be covered by $\aleph_0$ triangle-free graphs. Shelah (1987) showed that the existence of such a graph is consistent with ZFC, but no ZFC proof of existence (nor a proof that non-existence is also consistent, which would establish independence) has been located in post-2007 literature. The problem therefore remains open at the set-theoretic level.

Reviewer notes. The UCSD Erdős problems pages (mathweb.ucsd.edu) returned SSL errors and could not be fetched. Komjáth's ELTE publications page also returned a certificate error. The Komjáth–Shelah (1988) JSL paper on forcing constructions for uncountably chromatic graphs is closely related (it shows that the Erdős–Hajnal conjecture 'every κ-chromatic graph has a κ-chromatic triangle-free subgraph' can fail for κ=ℵ₁ in a forcing extension), but it predates 2007 and concerns a different (though nearby) problem. No post-2007 paper specifically addressing the ZFC status of the unions-of-triangle-free-graphs problem was found. Confidence is low because the problem lives in combinatorial set theory with sparse web coverage, and key resource pages were inaccessible.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 06) (web search enabled).

Problem. Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph · infinite graph · triangle free

Discussion

Shelah [S] has proved that the existence of such a graph is consistent with ZFC.

Bibliography

★ [EH] P. Erdos and A. Hajnal, On decomposition of graphs, Acta Math. Acad. Sci. Hungar. 18 (1967), 359–377.
[S] S. Shelah, Consistency of positive partition theorems for graphs and models, in Set Theory and Applications, Springer Lecture Notes 1401, (Toronto, ON, 1987), 167–193.