In der vorliegenden Arbeit wird hauptsachlich gezeigt, da13 die 4-chromen Graphen vie1 dichter mit vollstandigen 4-Graphen und ihre Unterteilungen durchdrungen sind, als bisher bekannt war.
1. Einleitung
Definitionen. Graph bedeutet eine Menge, deren Eleniente Knotenpunkte heiBen zusammen rnit einer Menge von ungeordneten Paaren verschiedener Knotenpunkte, genannt Kanten. Knotenpunkte werden durch a, b, usw. bezeichnet, Kanten durch (a, b) usw., wo a =+ b und (a, b) = (b, a ) . Die hier verwendete Terminologie ist die von D. KONIG [l]. Ein vollstandiger k-Graph ist ein Graph mit k ( 2 1) Knotenpunkten und k(k -1)/2 Kanten, er wird rnit {k} bezeichnet. Eine Unterteilung eines vollstandigen k-Graphen, k 2 2, ist ein Graph, der aus einem {k} entsteht, indem man Kanten des {k} beliebig oft durch Einsetzen neuer Knotenpunkte in zwei teilt. Solche Unterteilungen werden mit {k U } bezeichnet. Die k Knotenpunkte vom Grad k -1 heillen Verzweigungspunkte des {k}. Ein Graph heiBt k-farbbar, wenn seine Knotenpunkte in k paarweise elementfremde Klassen eingeteilt werden konnen, so da13 keine zwei Knotenpunkte, welche zu ein und derselben Klasse gehoren, durch eine Kante verbunden sind. Ein Graph heiBt k-chrom, wenn er k-fiirbbar und nicht (k -1)-farbbar ist. k nennt man dann die chromafische Zahl des Graphen.
I n jedem unendlichen k-ch,romen Graphen ist ein endlicher k-chromer Teilgraph enthalten [ 21.
r' + r ' ' bedeutet die Vereinigung der zwei Graphen r' und r", r' n F' bedeutet ihren Durchschnitt. Wenn die Knotenpunkte p , q, . . . , s zu den Graphen F gehoren, so bedeutet r -( p + q + . . + s) den Graphen, welcher aus r entsteht, wenn man p , q, . . . , s mitsamt allen Kanten, die rnit einem oder zwei dieser Knotenpunkte inzidieren, aus r streicht .
l ) Verfasser dankt der Vereinsbank Hamburg fur das ihm zur Verfiigung gestellte Forschungsstipendium.
I*