Uncountable-chromatic graphs have common \(4\)-chromatic subgraphs
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 4-chromatic subgraphs (proposed by
Erdös, Hajnal [1]):
Is it true that if \( G_1, G_2\) are \( \aleph_1\)-chromatic graphs then
they have a common \( 4\)-chromatic subgraph?
Erdös, Hajnal and Shelah [2] proved that any \( \omega_1\)-chromatic graph contains all cycles \( C_k\) for \( k > k_0\). Consequently, the above problem has an affirmative answer for 3-chromatic graphs.
Bibliography | |
---|---|
1 | P. Erdös and A. Hajnal, Chromatic number of finite and infinite graphs and hypergraphs, Special volume on order sets and their applications (L'Arbresle 1982), Discrete Math. 53 (1985), 281-285. |
2 | P. Erdös, A. Hajnal and S. Shelah, On some general properties of chromatic numbers, Topics in topology (Proc. Colloq., Keszthely, 1972); Colloq. Math. Soc. János Bolyai, Vol. 8, 243-255, North-Holland, Amsterdam, 1974. |