×

On chromatic number of infinite graphs. (English) Zbl 0164.24803

Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 83-98 (1968).
[For the entire collection see Zbl 0155.00201.]
Aus einem Hauptresultat der Arbeit folgt mit Hilfe der allgemeinen Kontinuumhypothese: Zu je 2 Ordinalzahlen \(\xi,k\) (\(k \geq 1\) endlich) existiert ein Graph \(G\) mit \(\alpha(G) = \aleph_{\xi+k}\) Ecken und mit der chromatischen Zahl \(\text{Chr(G)} = \aleph_{\xi+1}\), so daß \(\text{Chr}(G') < \text{Chr}(G)\) für jeden Teilgraph \(G'\subseteq G\) mit \(\alpha(G') < \alpha(G)\). Zu vorgegebenen Kardinalzahlen \(\alpha,\gamma\) (\(\alpha\) regulär) werden Graphen \(G_{\alpha ,\gamma}\) konstruiert, die im folgenden Sinne universal sind: (1) \(\alpha(G_\alpha,\gamma) = \alpha;\) (2) \(G'\subseteq G_{\alpha,\gamma}\), \(\alpha(G') = \alpha \Rightarrow \text{Chr}(G')\leq \gamma\); (3) Jeder Graph \(G\), der (1) und (2) (mit \(G\) statt \(G_{\alpha,\gamma}\)) erfüllt, ist einem Teilgraph von \(G_{\alpha,\gamma}\) isomorph.
Die Verff. zeigen weiter in Verschärfung eines Satzes von E. Milner, daß zu je 2 Ordinalzahlen \(\alpha,k\) (\(k \geq 1\) endlich) ein Mengensystem \((h,H)\) existiert mit: (a) \(h=\{\xi: 0\leq \xi < \omega_{\alpha+1}\}\) (b) \(X \in H\Rightarrow X\subseteq h\) und \(|X| = k\), (c) \(h'\subseteq h\), \(|h'| = \aleph_{\alpha+1} \Rightarrow\) es existiert ein \(X \in H\) mit \(X \subseteq h'\); (d) \(X,Y \in H\), \(\text{Max }X=\text{Max }Y \Rightarrow X=Y\) oder \(|X \cap Y| = 1;\) (e) \(X,Y \in H\), \(|X \cap Y| \geq 2\), \(a \in X \cap Y \Rightarrow a\) hat in \(X\) und \(Y\) bzgl. \(<\) die gleiche Höhe.
Die Verff. formulieren explizit 8 Probleme; dabei wird (s. Problem 4) auf einen Zusammenhang mit einem Problem von Kurepa hingewiesen.
Reviewer: H.A.Jung

MSC:

05C15 Coloring of graphs and hypergraphs

Keywords:

topology

Citations:

Zbl 0155.00201