Logarithmic Upper Bound for the Upper Chromatic Number of \(S(t, t + 1, v)\) Systems

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 \geq t+2\) always admit colorings with at least \(c\cdot v^\alpha\) colors, for some positive constants \(c\) and \(\alpha\), as \(v\to\infty\).