×

zbMATH — the first resource for mathematics

On coloring graphs to maximize the proportion of multicolored \(k\)-edges. (English) Zbl 0167.22302
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 \(G_k\) heißen. Man färbe die Punkte von \(G_k\) irgendwie mit \(l\) Farben. Man bestimme diejenigen \(k\)-Kanten von \(G_k\), die wenigstens einen Punkt jeder Farbe enthalten, und bilde die Quotienten der Zahl dieser Kanten und der Zahl aller \(k\)-Kanten von \(G_k\). Die größtmögliche so erhaltene Zahl (also bei allen \(l\)-Färbungen von \(G_k\)) wird mit \(p(G_k,l)\) bezeichnet. Weiter bezeichne \(m(n,k,l)\) den Minimalwert von \(p(G_k,l)\), wo \(G_k\) alle \(k\)-Graphen mit \(n\) Punkten durchläuft, und \(m(k,l)\) den Minimalwert aller \(p(G_k,l)\) mit \(G_k\) endlich. Es wird gezeigt, daß \(p(G_k,l) = m(n,k,l)\) gilt, wenn \(G_k\) der vollständige \(k\)-Graph mit \(n\) Punkten ist. Ferner wird die Abschätzung \(m(n,k,l) > S_2(k,l)\cdot l! \cdot l^{-k}\) bewiesen (wo \(S_2(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ß \(\lim_{k \to \infty} 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

MSC:
05C15 Coloring of graphs and hypergraphs
Keywords:
topology
PDF BibTeX XML Cite
Full Text: DOI