Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 164.24803
Autor: Erdös, Pál; Hajnal, András
Title: On chromatic number of infinite graphs (In English)
Source: Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 83-98 (1968).
Review: [For the entire collection see Zbl 155.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 Chr(G) = \aleph\xi+1, so daß Chr(G') < 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 ==> 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 ==> X\subseteq h und |X| = k, (c) h'\subseteq h, |h'| = \aleph\alpha+1 ==> es existiert ein X in H mit X \subseteq h'; (d) X,Y in H, Max X = Max Y ==> X = Y oder |X \cap Y| = 1; (e) X,Y in H, |X \cap Y| \geq 2, a in X \cap Y ==> 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
Classif.: * 05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag