The Open UniversitySkip to content

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.

Full text available as:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (152kB)
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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.

Item Type: Journal Item
ISSN: 0095-8956
Extra Information: 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.
Keywords: Graph colourings; cubic graphs; Steiner triple systems
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 3491
Depositing User: Fred Holroyd
Date Deposited: 27 Jun 2006
Last Modified: 03 May 2019 07:52
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU