Consistency results on infinite graphs (Q1117946): Difference between revisions

In this paper it is shown that it is consistent (with \(2^{\aleph_ 0}=\aleph_ 3)\) that there is an \(\aleph_ 2\)-chromatic graph of size \(\aleph_ 2\) which does not have an exactly \(\aleph_ 1\)-chromatic subgraph, by extending \textit{F. Galvin}'s result [Period. Math. Hung. 4, 117-119 (1973; Zbl 0278.05105)]. Another extension is the following one: it is consistent that \(2^{\aleph_ 0}=\aleph_ 2\) and there exists a graph X on \(\omega_ 2\) such that every subgraph of size \(\leq \aleph_ 1\) is countably chromatic, while there is no independent set of size \(\aleph_ 2\), therefore every subgraph of size \(\aleph_ 2\) is \(\aleph_ 2\)-chromatic. An old question of P. Erdős and A. Hajnal is whether it is true that every uncountably chromatic graph contains an uncountably chromatic \(\omega\)-connected subgraph. In the second part of this paper it is proved that it is consistent that there exists an \(\aleph_ 1\)-chromatic graph of size \(\aleph_ 1\) with no \(\omega\)- connected \(\aleph_ 1\)-chromatic subgraph and it is consistent that \(2^{\aleph_ 0}=\aleph_ 2\) and every \(\aleph_ 1\)-size, \(\aleph_ 1\)-chromatic graph contains an \(\omega\)-connected, \(\aleph_ 1\)- chromatic subgraph. Finally, using the method of the first part, it is proved that Singular Cardinal Compactness is consistently false for uncountable chromatic graphs: it is consistent that there exists a graph X of size \(\aleph_{\omega}\), with chromatic number equal to \(\aleph_ 1\) such that every subgraph of smaller cardinality is countably chromatic, thus solving a problem raised by \textit{S. Shelah} [Isr. J. Math. 21, 319-349 (1975; Zbl 0369.05034)].