Three-line chromatic indices of Steiner triple systems

Grannell, M. J.; Griggs, T. S. and Rosa, A. (2000). Three-line chromatic indices of Steiner triple systems. Australasian Journal of Combinatorics, 21, pp. 67–84.

Abstract

There are five possible structures for a set of three lines of a Steiner triple system. Each of these three-line ``configurations'' gives rise to a colouring problem in which a partition of all the lines of an STS( $v$ ) is sought, the components of the partition each having the property of not containing any copy of the configuration in question. For a three-line configuration $B$ , and STS( $v$ ) $S$ , the minimum number of classes required is denoted by $\chi(B,S)$ and is called the $B$ -chromatic index of $S$ . This generalises the ordinary chromatic index $\chi'(S)$ and the 2-parallel chromatic index $\chi''(S)$ . (For the latter see $\cite{DGGR}$ .) In this paper we obtain results concerning $\underline\chi(B,v)=\min\{\chi(B,S):S \mbox{ is an STS($v$)}\}$ for four of the five three-line configurations $B$ . In three of the cases we give precise values for all sufficiently large $v$ and in the fourth case we give an asymptotic result. The values of the four chromatic indices for $v\le13$ are also determined.