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.