Holroyd, Fred and Skoviera, Martin
Colouring of cubic graphs by Steiner triple systems.
Journal of Combinatorial Theory, Series B, 91(1),
Full text available as:
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.
||Some of the symbols may not have transferred correctly into this bibliographic record and/or abstract.---
The DOI leads direct to the article; the URL leads direct to the journal homepage.
||Graph colourings; cubic graphs; Steiner triple systems
||Mathematics, Computing and Technology > Mathematics and Statistics
||27 Jun 2006
||04 Dec 2010 13:51
Actions (login may be required)