Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 169.26601
Autor: Erdös, Pál; Hajnal, András
Title: On decomposition of graphs (In English)
Source: Acta Math. Acad. Sci. Hung. 18, 359-377 (1967).
Review: Die Graphen Gi = (Ei,Ki) (i in I) bestimmen eine Eckenzerlegung von G = (E,K), wenn die Eckenmengen Ei disjunkt sind, Gi von Ei in G aufgespannter Untergraph ist und \bigcupi in I Ei = E; sie bestimmen eine Kantenzerlegung, wenn E = Ei (i in I) und \bigcupi in I Ki = 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 Gi mit möglichst kleinen \beta (Gi) 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 Gi (i in I) mit |I| = \gamma < \alpha ein i in I mit \beta(Gi) > \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 Gn (n = 1,2,...) mit \beta(Gn) \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 Col(G) \leq \gamma ist. Im Fall \gamma < \omega ist Col(G) \leq 2\gamma notwendig. (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
Classif.: * 05C70 Factorization, etc.
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag