×

Problems and results in finite and infinite combinatorial analysis. (English) Zbl 0236.05120

In der Arbeit werden Kantenzerlegungen \(h= \bigcup_{\xi < \gamma} h_\xi\) von Graphen \(h\) betrachtet, wobei die \(h_\xi\) paarwise kantendisjunkte Graphen sind. \((g_1, \alpha) \to (g_2, \gamma)\) bedeutet, daß jeder Graph \(h\) mit \(\alpha\) Ecken, der keinen zu \(g_1\) isomorphen Teilgraphen enthält, eine Kantenzerlegung \(h= \bigcup_{\xi < \gamma} h_\xi\) zuläßt, wobei kein \(h_\xi\) einen zu \(g_2\) isomorphen Teilgraphen besitzt. Weiter bedeutet \(g \to (g_\xi)^2_\xi\), daß für jede Kantenzerlegung \(g= \bigcup_{\xi < \gamma} h_\xi\) mindestens ein \(h_\xi\) einen zu \(g_\xi\) isomorphen Teilgraphen besitzt. In dieser Notation wird über einige Ergebnisse und Probleme vom Ramsey-Typ berichtet: \((K_{\omega},\omega_2) \to (K_n, \omega)\) ist für \(n \geq 3\) ungeklärt; für natürliche Zahlen \(k,l\) wird die Existenz von \(n\) mit \((C_{2k-1},n) \nrightarrow (C_{2k+1},l)\) bewiesen, wobei \(C_m\) Kreis mit \(m\) Ecken; die Existenz von \(n\) mit \((K_k,n) \nrightarrow (K_{k-1},r)\) ist für \(r>3\) nicht bekannt. Eine Klasse \({\mathcal K}\) von Graphen hat die (uneingeschränkte) \(G-R\)-Eigenschaft, wenn zu jedem \(g \in {\mathcal K}\) (und jedem \(\gamma\)) ein \(h \in {\mathcal K}\) existiert, so daß \(h \to (g,g)(h \to (g_\xi)^2_\gamma\) mit \(g_\xi =g\) für alle \(\xi\)). Es werden mehrere Klassen in Bezug auf die (uneingeschränkte) \(G-R\)-Eigenschaft diskutiert und in diesem Zusammenhang weitere Probleme formuliert.
Reviewer: H.A.Jung

MSC:

05C99 Graph theory
05A99 Enumerative combinatorics
00A07 Problem books
PDFBibTeX XMLCite
Full Text: DOI