Journal article
The strong chromatic number of partial triple systems
Abstract
A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum …
Authors
Colbourn CJ; Jungnickel D; Rosa A
Journal
Discrete Applied Mathematics, Vol. 20, No. 1, pp. 31–38
Publisher
Elsevier
Publication Date
5 1988
DOI
10.1016/0166-218x(88)90039-x
ISSN
0166-218X