Vertex colorings of Steiner systems S (t, t + 1, v) are considered in which each block contains at least two vertices of the same color. Necessary conditions for the existence of such colorings with given parameters are determined, and an upper bound of the order O(ln v) is found for the maximum number of colors. This bound remains valid for nearly complete partial Steiner systems, too. In striking contrast, systems S(t, k, v) with k >= t + 2 always admit colorings with at least c v^(\alpha) colors, for some positive constants c and \alpha, as v -> \infinity.

Logarithmic upper bound for the upper chromatic number of S(t, t+1, v) systems

MILAZZO, Lorenzo Maria Filippo;
2009-01-01

Abstract

Vertex colorings of Steiner systems S (t, t + 1, v) are considered in which each block contains at least two vertices of the same color. Necessary conditions for the existence of such colorings with given parameters are determined, and an upper bound of the order O(ln v) is found for the maximum number of colors. This bound remains valid for nearly complete partial Steiner systems, too. In striking contrast, systems S(t, k, v) with k >= t + 2 always admit colorings with at least c v^(\alpha) colors, for some positive constants c and \alpha, as v -> \infinity.
2009
Mixed hypergraph; Steiner system; vertex coloring; Upper chromatic number
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/10100
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact