Steiner triple systems with high chromatic index

Darryn Bryant, Charles J. Colbourn, Daniel Horsley, Ian M. Wanless

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


It has been conjectured that every Steiner triple system of order v 6= 7 has chromatic index at most (v + 3)=2 when v = 3 (mod 6) and at most (v + 5)=2 when v = 1 (mod 6). Herein, we construct a Steiner triple system of order v with chromatic index at least (v + 3)=2 for each integer v = 3 (mod 6) such that v ≥ 15, with four possible exceptions. We further show that the maximum number of disjoint parallel classes in the systems constructed is sublinear in v. Finally, we establish for each order v ≥ 15 (mod 18) that there are at least vv2(1=6+o(1)) nonisomorphic Steiner triple systems with chromatic index at least (v + 3)=2 and that some of these systems are cyclic.

Original languageEnglish
Pages (from-to)2603-2611
Number of pages9
JournalSIAM Journal on Discrete Mathematics
Issue number4
Publication statusPublished - 2017


  • Block coloring
  • Chromatic index
  • Parallel class
  • Steiner triple system

Cite this