Steiner triple systems with high chromatic index

Abstract

It is conjectured that every Steiner triple system of order $v\ne 7$ has chromatic index at most $(v+3)/2$ when $v\equiv 3(\mathrm{mod}6)$ and at most $(v+5)/2$ when $v\equiv 1(\mathrm{mod}6)$. Herein, we construct a Steiner triple system of order $v$ with chromatic index at least $(v+3)/2$ for each integer $v\equiv 3(\mathrm{mod}6)$ such that $v\ge 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\equiv 15(\mathrm{mod}18)$ that there are at least $v^{v^2(1/6+o(1))}$ non-isomorphic Steiner triple systems with chromatic index at least $(v+3)/2$ and that some of these systems are cyclic.

10 pages, 0 figures

Cited by in corpus (2)

• Extremal Set Theory and LWE Based Access Structure Hiding Verifiable Secret Sharing with Malicious-Majority and Free Verification
• New bounds on the size of Nearly Perfect Matchings in almost regular hypergraphs