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
No digital document available to download for this item

Item Actions