The Open UniversitySkip to content
 

A Steiner triple system which colours all cubic graphs

Grannell, Mike; Griggs, Terry; Knor, Martin and Skoviera, Martin (2004). A Steiner triple system which colours all cubic graphs. Journal of Graph Theory, 46(1) pp. 15–24.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1002/jgt.10166
Google Scholar: Look up in Google Scholar

Abstract

We prove that there is a Steiner triple system such that every simple cubic graph can have its edges colored by points of in such a way that for each vertex the colors of the three incident edges form a triple in . This result complements the result of Holroyd and koviera that every bridgeless cubic graph admits a similar coloring by any Steiner triple system of order greater than 3. The Steiner triple system employed in our proof has order 381 and is probably not the smallest possible.

Item Type: Journal Article
ISSN: 0364-9024
Keywords: cubic graphs; coloring; Steiner triple system
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 2148
Depositing User: Mike Grannell
Date Deposited: 06 Jun 2006
Last Modified: 02 Dec 2010 19:46
URI: http://oro.open.ac.uk/id/eprint/2148
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk