Computing the Chromatic Index of Steiner Triple Systems

A Steiner triple system of order v, denoted STS (v), is a pair (V, B); V is a u-set of elements and B is a collection of 3-subsets of V called blocks. Each unordered pair of elements is contained in precisely one block. There is a substantial body of research on STS, partially because of their wide applicability in the design of experiments, and in the theory of error-correcting codes. In the design of statistical experiments, each block corresponds to a 'test' of the three elements in the block. In this context, we can view disjoint blocks as tests which can be carried out simultaneously. In terms of STS, we define a colour class to be a set of pairwise disjoint blocks. A k-block colouring is a partition of the block set into k colour classes; the chromatic index is the least k for which such a colouring exists. In our example, the chromatic index is precisely the time required for the entire experiment. In other applications of STS, similar reasons exist for studying the chromatic index. The chromatic index of STS is also a problem of some interest in combinatorics as a restriction of certain investigations of set systems. In computer science, further motivation arises from the substantial interest in the chromatic index of graphs, and applications in scheduling (see Ref. 5 and references therein). The purpose of this note is to describe a method for computing the chromatic index of STS, and to describe results obtained in testing this method on small STS.