Infinite \(K_{4}\)-free graphs are the union of triangle-free countable graphs
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A problem on the decomposition of graphs ($250, proposed by
Erdös and Hajnal [1]):
Is there an infinite graph \( G\) which contains no \( K_4\) and which is not the
union of \( \aleph_0\) graphs which are triangle-free?
Shelah [2] proved that the existence of such a graph is consistent but it is not known if this is provable in ZFC (also see 1).
Bibliography | |
---|---|
1 | P. Erdös and A. Hajnal, On decomposition of graphs, Acta Math. Acad. Sci. Hungar. 18 (1967), 359-377. |
2 | 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. |