Colouring of cubic graphs by Steiner triple systems

Holroyd, Fred and Skoviera, Martin (2004). Colouring of cubic graphs by Steiner triple systems. Journal of Combinatorial Theory, Series B, 91(1) pp. 57–66.

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.

Viewing alternatives

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About