Universal Steiner triple systems

Definitions and mathematical statement

A finite Steiner triple system is a pair $(S,\mathcal B)$ in which $S$ is a finite set of points and $\mathcal B$ is a family of three-element subsets, called blocks, such that every unordered pair of distinct points belongs to exactly one block. Distinct points in a block are part of the definition; repeated-point triples are not allowed.

Let $G$ be a finite simple cubic graph, so each vertex is incident with exactly three edges. An $(S,\mathcal B)$-edge-coloring is a map $c:E(G)\to S$ such that, at every vertex with incident edges $e_1,e_2,e_3$, the set $\{c(e_1),c(e_2),c(e_3)\}$ is a block of $\mathcal B$. In particular those three colors must be distinct, so the map is an ordinary proper edge-coloring with an additional local triple restriction. The same point of $S$ may color multiple nonincident edges.

The problem is to characterize all finite Steiner triple systems having the following universal property: every finite simple cubic graph admits an $(S,\mathcal B)$-edge-coloring. Cubic graphs with bridges are included, and no connectedness assumption is imposed. Requiring connected cubic graphs would give the same property, since colorings of components can be combined.

A characterization should give necessary and sufficient conditions on the triple system, and prove both directions. Establishing that one system colors a finite list of graphs does not establish the universal property. Likewise, the ability to color all bridgeless cubic graphs is a weaker requirement than the one stated here.

Short English statement

Which finite Steiner triple systems supply edge colors for every cubic graph so that the three colors at each vertex form a block?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3201 (OPG-624), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Universal Steiner triple systems. Original problem and discussion. http://www.openproblemgarden.org/op/universal_steiner_triple_systems.