What must and what need not be contained in a graph of uncountable chromatic number? (Q794660): Difference between revisions

This paper is concerned with the subgraphs of a graph with chromatic number \(\geq \aleph_ 1\). It is known that every such graph must contain as a subgraph the complete bipartite graphs \(K_{\aleph_ 1,i}\) for each finite i (and so in particular contain a 4-cycle); on the other hand for each finite i there are graphs with chromatic number \(\aleph_ 1\) which contain no cycles of odd length \(\leq i\). (See \textit{P. Erdős} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 17, 61-99 (1966; Zbl 0151.337)].) This paper considers two very similar graphs \(\Gamma\) and \(\Delta\), where \(\Gamma\) is the graph on vertex set \(\{a\}\cup \{x_ i,y_ i\); \(i<\omega \}\) with each \(y_ i\) joined to \(\{x_ 0,...,x_{i-1}\}\) and a joined to \(\{x_ i\); \(i<\omega \}\), and \(\Delta\) is the graph on vertex set \(\{a,b\}\cup \{x_ i,y_ i\); \(i<\omega \}\) with again each \(y_ i\) joined to \(\{x_ 0,...,x_{i- 1}\}\) and both a, b joined to \(\{x_ i\); \(i<\omega \}\). The authors show that every graph with chromatic number \(\geq \aleph_ 1\) contains a subgraph isomorphic to \(\Gamma\), but using CH they construct a graph (on \(\aleph_ 1\) vertices) with chromatic number \(\aleph_ 1\) which has no subgraph isomorphic to \(\Delta\).