Home » Subject » Graph Theory » Infinite Graphs

Unions of triangle free graphs

Importance: High ✭✭✭
Author(s): Erdos, Paul
Hajnal, Andras
Subject: Graph Theory
» Infinite Graphs
Keywords: forbidden subgraph
infinite graph
triangle free
Recomm. for undergrads: no
Prize: $250 (Erdos - Graham)
Posted by: mdevos
on: June 4th, 2007
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?

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.


* indicates original appearance(s) of problem.
add new comment