×

On chromatic number of graphs and setsystems. (English) Zbl 0151.33701

Für Mengensysteme \({\mathcal H} = (h,H)\) \((A \in H \Rightarrow A \subseteq h\)) bezeichnet \(\text{Col}({\mathcal H})\) die kleinste Kardinalzahl \(\alpha\), zu der eine Wohlordnung \(\prec\) von \(h\) mit \(|\bigcup A \in H\), \(x = \text{Max}_{\prec} A\), \(A-\{x\}| < \alpha\) für alle \(x \in h\) existiert. Die chromatische Zahl \(\text{Chr}({\mathcal H})\) ist die kleinste Kardinalzahl \(\alpha\), zu der eine Darstellung \(h = \bigcup_{i \in I} h_i\) mit \(|I| = \alpha\) und \(A \not\subseteq h_i\), (\(A \in H, i\in I\)) existiert. Für \({\mathcal H}=(h,H)\) mit \(2 \leq |A| < \omega_0\) \((A \in H)\) wird zunächst \(\text{Chr}({\mathcal H} \leq \text{Col}({\mathcal H})\) gezeigt. Die Autoren beweisen, daß Graphen \({\mathcal G}\) mit \(\text{Col}({\mathcal G}) > \omega_0\) große vollständige paare Graphen enthalten. Hieraus folgt speziell, daß ein Graph \({\mathcal G}\) mit \(\text{Col}({\mathcal G}) > \omega_0\) gerade Kreise jeder Länge enthält. Sie zeigen weiter, daß \(\text{Chr}({\mathcal G}) \leq 2j < \omega_0\) gilt, falls \({\mathcal G}\) keine Kreise der Länge \(2i+1\) \((i \geq j)\) enthält; für \(\beta \geq \omega_0\) und \(j \geq 1\) konstruieren sie anderseits Graphen \({\mathcal G}_{\beta,j}\) mit \(\text{Chr}({\mathcal 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. \(\text{Col}({\mathcal G})\) richtig ist (Zbl 0044.38203), wird negativ beantwortet: Aus \(\text{Col}({\mathcal G}') \leq \beta\) für jeden endlichen Teilgraph \({\mathcal G}'\) von \({\mathcal G}\) folgt \(\text{Col}({\mathcal 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<\omega_0\) Mengensysteme \({\mathcal H} = (h,H)\) mit \(|A| = k\) \((A \in H)\) behandelt; für diese wird der Begriff \(s\)-kreisfrei (\(I \leq s < \omega_0\)) eingeführt. Das Hauptergebnis hierüber liefert als Korallar: Zu \(k,r,s, < \omega_0\) existieren \(s\)-kreisfreie \({\mathcal H} = (h,H)\) mit \(\text{Chr}({\mathcal H}) \geq r\) und \(|A| = k\) (\(A \in H\)). Dies verallgemeinert ein Ergebnis des ersten Verf. (Zbl 0084.39602). In der Einleitung wird ein Abriß der Geschichte der behandelten Probleme gegeben.
Reviewer: H.A.Jung

MSC:

05C15 Coloring of graphs and hypergraphs

Keywords:

topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. Berge,Thèorie des graphes et ses application (Paris, Dunod, 1958). · Zbl 0214.50804
[2] N. G. de Bruijn andP. Erdos, A colour problem for infinite graphs and a problem in the theory of relations,Indag. Math.,13 (1951), pp. 371–373.
[3] G. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc., (3),2 (1952), pp. 69–81. · Zbl 0047.17001
[4] P. Erdos, Graph theory and probability,Canad. J. Math.,11 (1959), pp. 34–38. · Zbl 0084.39602
[5] P. Erdos andA. Hajnal, On a property of families of sets,Acta Math. Acad. Sci. Hung.,12 (1961), pp. 87–123. · Zbl 0201.32801
[6] P. Erdos andA. Hajnal, Some remarks on set theory IX,Michigan Math. Journal,11 (1964), pp. 107–127.
[7] P. Erdos andR. Rado, A construction of graphs without triangles having pre-assigned order and chromatic number,The Journal of the London Math. Soc.,35 (1960), pp. 445–448. · Zbl 0097.16402
[8] G. Fodor, Proof of a conjecture of P. Erdos,Acta Sci. Math.,14 (1951), pp. 219–227. · Zbl 0048.28202
[9] T. Gallai, Graphen mit triangulierbaren ungeraden Vielecken,Publ. Math. Inst. Hung.,7. A. (1962), pp. 3–36. · Zbl 0132.21101
[10] H. J. Kiesler andA. Tarski, From accessible to inaccessible cardinals,Fundamenta Mathematicae,53 (1964), pp. 225–307.
[11] E. W. Miller, On a property of families of sets,Comptes Rendus Varsowie,30 (1937), pp. 31–38. · JFM 63.0832.01
[12] J. Mycielski, Sur le coloriege des graphs,Colleg. Math.,3 (1955), pp. 161–162. · Zbl 0064.17805
[13] A. Tarski, Sur la decomposition des ensembles en sous ensembles presque disjoint,Fundamenta Math.,14 (1929), pp. 205–215. · JFM 55.0053.04
[14] Blanche Descartes, ”A three colour problem”,Eureka (April 1947) (Solution March 1948) and ”Solution to Advanced Problem No. 4526”,Amer. Math. Monthly,61 (1954), p. 352.
[15] P. Erdos, On circuits and subgraphs of chromatic graphs,Mathematika,9 (1962), pp. 170–175. · Zbl 0109.16502
[16] A. Hajnal, On the topological product of discrete spaces,Notices of the Amer. Math. Soc.,11 (1964), p. 578; and On the {\(\alpha\)}-incompactness of the topological product of discrete spaces and some related problems,Fundamenta Mathematicae (to appear).
[17] P. Erdos, A. Hajnal andR. Rado, Partition relations for cardinal numbers,Acta Math. Acad. Sci. Hung.,16 (1965), pp. 93–196. · Zbl 0158.26603
[18] A. W. Hales andR. I. Jewett, Regularity and positional games,Trans. Amer. Math. Soc.,106 (1963), pp. 222–229. · Zbl 0113.14802
[19] A. A. Zykov, On some properties of linear complexes,Russian Math. Sbornik, N. S. 24 (66) (1949), pp. 163–188.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.