Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 151.33701
Autor: Erdös, Pál; Hajnal, András
Title: On chromatic number of graphs and setsystems (In English)
Source: Acta Math. Acad. Sci. Hung. 17, 61-99 (1966).
Review: Für Mengensysteme H = (h,H) (A in H ==> A \subseteq h) bezeichnet Col(H) die kleinste Kardinalzahl \alpha, zu der eine Wohlordnung \prec von h mit |\bigcup A in H, x = Max\prec A, A-{x}| < \alpha für alle x in h existiert. Die chromatische Zahl Chr(H) ist die kleinste Kardinalzahl \alpha, zu der eine Darstellung h = \bigcupi in I hi mit |I| = \alpha und A \not\subseteq hi, (A in H, i in I) existiert. Für H = (h,H) mit 2 \leq |A| < \omega0 (A in H) wird zunächst Chr(H \leq Col(H) gezeigt. Die Autoren beweisen, daß Graphen G mit Col(G) > \omega0 große vollständige paare Graphen enthalten. Hieraus folgt speziell, daß ein Graph G mit Col(G) > \omega0 gerade Kreise jeder Länge enthält. Sie zeigen weiter, daß Chr(G) \leq 2j < \omega0 gilt, falls G keine Kreise der Länge 2i+1 (i \geq j) enthält; für \beta \geq \omega0 und j \geq 1 konstruieren sie anderseits Graphen G\beta,j mit Chr(G\beta,j) = \beta, die keine Kreise der Länge 2i+1 (1 \leq i \leq j) enthalten.
Ein Problem von R. Rado, ob das Analogon zum Satz von N.G.de Bruijn und dem ersten Verf. bzgl. Col(G) richtig ist (Zbl 044.38203), wird negativ beantwortet: Aus Col(G') \leq \beta für jeden endlichen Teilgraph G' von G folgt Col(G) \leq 2\beta -2 ( \leq 2 \beta -3 ist im allgemeinen falsch). Ähnliche Fragestellungen werden teils beantwortet, teils als Probleme formuliert. Schließlich werden für 2 \leq k < \omega0 Mengensysteme H = (h,H) mit |A| = k (A in H) behandelt; für diese wird der Begriff s-kreisfrei (I \leq s < \omega0) eingeführt. Das Hauptergebnis hierüber liefert als Korallar: Zu k,r,s, < \omega0 existieren s-kreisfreie H = (h,H) mit Chr(H) \geq r und |A| = k (A in H). Dies verallgemeinert ein Ergebnis des ersten Verf. (Zbl 084.39602). In der Einleitung wird ein Abriß der Geschichte der behandelten Probleme gegeben.
Reviewer: H.A.Jung
Classif.: * 05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag