Graph-theory open problems

Universal Steiner triple systems

Medium ★★ Graph Theory » Coloring » Edge coloring
Authors: Grannell, Mike, Griggs, Terry, Knor, Martin, Skoviera, Martin— posted by macajova on 2007-10-05

Status partial medium confidence

The preprint [KMPS] cited on the OPG page was published in 2010 in the Canadian Journal of Mathematics, formally establishing that every non-projective, non-affine, non-trivial point-transitive Steiner triple system is universal. A 2013 paper by Grannell, Griggs, Máčajová, and Škoviera addressed point-intransitive systems, constructing both an infinite family of universal point-intransitive STS containing no proper universal subsystem and an infinite family of non-universal STS that are neither projective nor affine; however, a complete characterization of all universal Steiner triple systems remains open.

Cited literature (1)

Reviewer notes. Multiple search results consistently report a 2013 paper by Grannell, Griggs, Máčajová, Škoviera ('Coloring cubic graphs by point-intransitive Steiner triple systems', J. Graph Theory 74, 163–181, DOI 10.1002/jgt.21696) that extends results to point-intransitive STS; however, all attempts to fetch this paper's URL returned HTTP 403, so it is not included in since_posted per the verification rule. The Kral et al. result appeared as a preprint when the OPG was posted but only the published (2010) journal version is cited here. No arXiv preprints on this topic were found. The full classification of which Steiner triple systems are universal (including non-point-transitive ones) appears to remain open.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 02) (web search enabled).

Problem. Which Steiner triple systems are universal?
Keywords: cubic graph · Steiner triple system

Discussion

A cubic graph $ G $ is $ S $ -edge-colorable for a Steiner triple system $ S $ if its edges can be colored with the points of $ S $ in such a way that the points assigned to three edges sharing a vertex form a triple in $ S $ . A Steiner triple system $ S $ is called universal if any (simple) cubic graph is $ S $ -colorable. It is easy to see that if $ S_3 $ denotes the trivial Steiner triple system with three points and one triple, then $ S_3 $ -colorable graphs are precisely (cubic) edge-3-colorable graphs. For the same reason, any cubic edge-3-colorable graph is $ S $ -colorable for any Steiner triple system (with at least one edge). Thus, the study of $ S $ -colorings may be viewed as an attempt to understand snarks . It is not hard to see, that a graph is Fano-colorable iff it has a nowhere-zero 8-flow. Thus (by Jaeger's result) Fano plane is "almost universal": it is possible to use it to color any bridgeless cubic graph (but it doesn't work for any graph with a bridge). Grannell et al. [GGKS] constructed a universal Steiner triple system of order 381. Holroyd, Skoviera [HS] proved that neither projective nor affine Steiner triple systems are universal. Kral et al. [KMPS] proved that any non-affine non-projective non-trivial point-transitive Steiner triple system is universal.

Bibliography

  • ★ [GGKS] M.J. Grannell, T.S. Griggs, M. Knor, M. Skoviera, A Steiner triple system which colours all cubic graphs , J. Graph Theory 46 (2004), 15--24. MathSciNet MathSciNet
  • [HS] F. Holroyd and M. Skoviera, Colouring of cubic graphs by Steiner triple systems , J.~Combin. Theory Ser. B 91 (2004), 57--66.
  • [KMPS] D. Kral, E. Macajova, A. Por, J.-S. Sereni, Characterization results for Steiner triple systems and their application to edge-colorings of cubic graphs , preprint.