Importance: Medium ✭✭
 Author(s): Grannell, Mike Griggs, Terry Knor, Martin Skoviera, Martin
 Subject: Graph Theory » Coloring » » Edge coloring
 Keywords: cubic graph Steiner triple system
 Posted by: macajova on: October 5th, 2007
Problem   Which Steiner triple systems are universal?

A cubic graph is -edge-colorable for a Steiner triple system if its edges can be colored with the points of in such a way that the points assigned to three edges sharing a vertex form a triple in .

A Steiner triple system is called universal if any (simple) cubic graph is -colorable.

It is easy to see that if denotes the trivial Steiner triple system with three points and one triple, then -colorable graphs are precisely (cubic) edge-3-colorable graphs. For the same reason, any cubic edge-3-colorable graph is -colorable for any Steiner triple system (with at least one edge). Thus, the study of -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

[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.

* indicates original appearance(s) of problem.