Star chromatic numbers of hypergraphs and partial Steiner triple systems (Q1903717): Difference between revisions

Author summary: The concept of star chromatic number of a graph introduced by \textit{A. Vince} [J. Graph Theory 12, No. 4, 551-559 (1988; Zbl 0658.05028)] is a natural generalization of the chromatic number of a graph. This concept was studied from a pure combinatorial point of view by \textit{J. A. Bondy} and \textit{P. Hell} [J. Graph Theory 14, No. 4, 479-482 (1990; Zbl 0706.05022)]. In this paper we introduce strong and weak star chromatic numbers of uniform hypergraphs and study their basic properties. In particular, we focus on partial Steiner triple systems (PSTS) for the weak case. We also discuss the computational complexity of finding a \((k,d)\)-colouring for a PSTS and construct, for every rational \(k/d > 2\), a \((k/d)\)-star chromatic PSTS.