Copy the page URI to the clipboard
Holroyd, Fred and Skoviera, Martin
(2004).
DOI: https://doi.org/10.1016/j.jctb.2003.10.003
URL: http://www.elsevier.com/wps/find/journaldescriptio...
Abstract
Let S be a Steiner triple system and G a cubic graph. We say that G is S-colourable if its edges can be coloured so that at each vertex the incident colours form a triple of S. We show that if S is a projective system PG(n, 2), n >= 2, then G is S-colourable if and only if it is bridgeless, and that every bridgeless cubic graph has an S-colouring for every Steiner triple system of order greater than 3. We establish a condition on a cubic graph with a bridge which ensures that it fails to have an S-colouring if S is an affine system, and we conjecture that this is the only obstruction to colouring any cubic graph with any non-projective system of order greater than 3.