Upper Chromatic Number of Steiner Triple Systems

Abstract

The upper chromatic number \(\overline{\chi}_u(\mathcal{H})\) of a \(C\)-hypergraph \(\mathcal{H} = (X, C)\) is the maximum number of colors that can be assigned to the vertices of \(\mathcal{H}\) in such a way that each \(C \in \mathcal{C}\) contains at least a monochromatic pair of vertices. This paper gives an upper bound for the upper chromatic number of Steiner triple systems of order \(n\) and proves that it is best possible for any \(n (\equiv 1 \text{ or } 3 \pmod{6})\).