Some $NP$-Completeness Results on Partial Steiner Triple Systems and Parallel Classes

Abstract

The complexity of determining if a Steiner triple system on $v=6n+3$ points contains a parallel class is currently unknown. In this paper, we show that the problem of determining if a partial Steiner triple system on $v=6n+3$ points contains a parallel class is NP-complete. We also consider the problem of determining the chromatic index of a partial Steiner triple system and show that this problem is NP-hard.