Universal Steiner triple systems

Recomm. for undergrads: no
Posted by: macajova
on: October 5th, 2007

\begin{problem} Which \href [Steiner triple systems]{http://mathworld.wolfram.com/SteinerTripleSystem.html} are universal? \end{problem}

A cubic graph $G$ is \emph{$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 \emph{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 \Def[snarks]{snark (graph theory)}.

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 \cite{HS} proved that neither projective nor affine Steiner triple systems are universal. Kral et al. \cite{KMPS} proved that any non-affine non-projective non-trivial point-transitive Steiner triple system is universal.


*[GGKS] M.J. Grannell, T.S. Griggs, M. Knor, M. Skoviera, \textit{A Steiner triple system which colours all cubic graphs}, J. Graph Theory \textbf{46} (2004), 15--24. \MRhref{MR2051465}

[HS] F. Holroyd and M. Skoviera, \textit{Colouring of cubic graphs by Steiner triple systems}, J.~Combin. Theory Ser. B \textbf{91} (2004), 57--66.

[KMPS] D. Kral, E. Macajova, A. Por, J.-S. Sereni, \textit{Characterization results for Steiner triple systems and their application to edge-colorings of cubic graphs}, preprint.

* indicates original appearance(s) of problem.