Star chromatic numbers of hypergraphs and partial Steiner triple systems (Q1903717)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Star chromatic numbers of hypergraphs and partial Steiner triple systems |
scientific article |
Statements
Star chromatic numbers of hypergraphs and partial Steiner triple systems (English)
0 references
26 August 1996
0 references
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.
0 references
star chromatic number
0 references
hypergraphs
0 references
partial Steiner triple systems
0 references
computational complexity
0 references