Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 167.22302
Autor: Erdös, Pál; Kleitman, Daniel J.
Title: On coloring graphs to maximize the proportion of multicolored k-edges (In English)
Source: J. Comb. Theory 5, 164-169 (1968).
Review: Die Verff. definieren als k-Graph eine Menge S, deren Elemente Punkte heißen, zusammen mit einer Menge von k-elementigen Teilmengen von S, die k-Kanten von Gk heißen. Man färbe die Punkte von Gk irgendwie mit l Farben. Man bestimme diejenigen k-Kanten von Gk, die wenigstens einen Punkt jeder Farbe enthalten, und bilde die Quotienten der Zahl dieser Kanten und der Zahl aller k-Kanten von Gk. Die größtmögliche so erhaltene Zahl (also bei allen l-Färbungen von Gk) wird mit p(Gk,l) bezeichnet. Weiter bezeichne m(n,k,l) den Minimalwert von p(Gk,l), wo Gk alle k-Graphen mit n Punkten durchläuft, und m(k,l) den Minimalwert aller p(Gk,l) mit Gk endlich. Es wird gezeigt, daß p(Gk,l) = m(n,k,l) gilt, wenn Gk der vollständige k-Graph mit n Punkten ist. Ferner wird die Abschätzung m(n,k,l) > S2(k,l)· l! · l-k bewiesen (wo S2(k,l) eine Stirling-Zahl zweiter Art ist). Im Spezialfall, daß n durch l teilbar ist, wird m(n,k,l) exakt angegeben. Als weitere Folgerung ergibt sich zum Beispiel, daß limk ––> oo m(k,l) = 1 (für jedes l) ist; für hinreichend großes k gibt es also für jeden k-Graphen Färbungen mit l Farben, so daß die meisten k-Kanten alle Farben enthalten. Weitere möglichen Verallgemeinerungen werden diskutiert.
Reviewer: R.Halin
Classif.: * 05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag