×

On decomposition of graphs. (English) Zbl 0169.26601

Die Graphen \(G_i=(E_i,K_i)\) \((i \in I)\) bestimmen eine Eckenzerlegung von \(G=(E,K)\), wenn die Eckenmengen \(E_i\) disjunkt sind, \(G_i\) von \(E_i\) in \(G\) aufgespannter Untergraph ist und \(\bigcup_{i \in I} E_i=E\); sie bestimmen eine Kantenzerlegung, wenn \(E=E_i\) \((i \in I)\) und \(\bigcup_{i \in I} K_i=K\). Die kleinste Kardinalzahl \(\beta\), so daß \(G\) keinen vollständigen Graphen \((\beta)\) enthält, werde mit \(\beta(G)\) bezeichnet. Die Verff. gehen von der Aufgabe aus, Graphen in möglichst wenige \(G_i\) mit möglichst kleinen \(\beta (G_i)\) zu zerlegen.
Aus den angegebenen Konstruktionen folgen die ”negativen” Resultate: 1. (Die allgemeine Kontinuumshypothese wird benutzt.) Zu Kardinalzahlen \(\alpha \geq \beta > \delta \geq 2\) (\(\alpha\) unendlich) existiert ein Graph \(G\) mit \(\alpha\) Ecken und \(\beta(G) = \beta\), so daß zu jeder Eckenzerlegung \(G_i\) \((i\in I)\) mit \(|I| = \gamma < \alpha\) ein \(i \in I\) mit \(\beta(G_i) > \delta\) existiert. 2. Das analoge Resultat für Kantenzerlegung bei festem unendlichem \(\gamma\) mit \(\alpha = (2^{(2^\alpha)^+})^+\) und \(\beta=\omega\). Ist andererseits \(3 \leq \beta(G) = \beta+1 < \omega\) und enthält \(G\) keinen Graphen mit \(\beta+1\) Ecken und \(\binom{\beta+1}{2}-1\) Kanten, so existiert eine Eckenzerlegung \(G_n\) \((n=1,2,...)\) mit \(\beta(G_n) \leq \beta\). Die Verff. untersuchen weiter, wann \(G\) eine Kantenzerlegung in \(\gamma\) Bäume zuläßt. Ist \(\gamma\) unendlich, so ist dies genau dann der Fall, wenn \(\text{Col}(G) \leq \gamma\) ist. Im Fall \(\gamma < \omega\) ist \(\text{Col}(G) \leq 2\gamma\) notwendig. (\(\text{Col}(G)\) ist die kleinste Kardinalzahl \(\beta\), zu der eine Wohlordnung der Eckenmenge existiert, so daß der Grad ”nach unten” für alle Ecken \(< \beta\) ist.) Vier Probleme werden gestellt.
Reviewer: H.A.Jung

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos andA. Hajnal, On chromatic number of graphs and set-systems,Acta Math. Acad. Sci. Hung.,17 (1966), pp. 61–99. · Zbl 0151.33701
[2] P. Erdos andR. Rado, A partition calculus in set theory,Bulletin of Am. Math. Soc.,62 (1956), pp. 427–489. · Zbl 0071.05105
[3] P. Erdos, A. Hajnal andR. Rado, Partition relations for cardinal numbers,Acta Math. Acad. Sci. Hung.,16 (1965), pp. 93–196. · Zbl 0158.26603
[4] 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
[5] P. Erdos, Graph theory and probability,Canad. J. Math.,11 (1959), pp. 34–38. · Zbl 0084.39602
[6] P. Erdos andA. Rogers, The construction of certain graphs,Canadian Math. Journal,14 (1962), pp. 702–707. · Zbl 0194.25304
[7] E. Specker, Teilmengen von Mengen mit Relationen,Commentarii Math. Helvetici,31 (1957), pp. 302–334. · Zbl 0080.03703
[8] Nash Williams, Decomposition of finite graphs into forests,Journal of the London Math. Soc.,39 (1964), p. 12. · Zbl 0119.38805
[9] C. Berge,Théorie des graphes et ses applications (Dunod, Paris, 1958).
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.