Coloring cubic graphs by point-intransitive Steiner triple systems

Grannell, Mike J.; Griggs, Terry S.; Máčajová, Edita and Škoviera, Martin (2013). Coloring cubic graphs by point-intransitive Steiner triple systems. Journal of Graph Theory, 74(2) pp. 163–181.




An $\cs$-colouring of a cubic graph $G$ is an edge-colouring of $G$ by points of a Steiner triple system $\cs$ such that the colours of any three edges meeting at a vertex form a block of $\cs$. A Steiner triple system which colours every simple cubic graph is said to be universal. It is known that every non-trivial point-transitive Steiner triple system that is neither projective nor affine is universal. In this paper we present the following results.

(1) We give a sufficient condition for a Steiner triple system $\cs$ to be universal.

(2) With the help of this condition we identify an infinite family of universal point-intransitive Steiner triple systems that contain no proper universal subsystem. Only one such system was previously known.

(3) We construct an infinite family of non-universal Steiner triple systems none of which is either projective or affine, disproving a conjecture made by Holroyd and the last author in 2004.

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions