The Open UniversitySkip to content
 

Coloring cubic graphs by point-intransitive Steiner triple systems

Grannell, Mike J.; Griggs, Terry S.; Máčajová, Edita and Škoviera, Martin (2013). Coloring cubic graphs by point-intransitive Steiner triple systems. Journal of Graph Theory, 74(2) pp. 163–181.

URL: http://onlinelibrary.wiley.com/doi/10.1002/jgt.216...
DOI (Digital Object Identifier) Link: https://doi.org/10.1002/jgt.21698
Google Scholar: Look up in Google Scholar

Abstract

An $\cs$-colouring of a cubic graph $G$ is an edge-colouring of $G$ by points of a Steiner triple system $\cs$ such that the colours of any three edges meeting at a vertex form a block of $\cs$. A Steiner triple system which colours every simple cubic graph is said to be universal. It is known that every non-trivial point-transitive Steiner triple system that is neither projective nor affine is universal. In this paper we present the following results.

(1) We give a sufficient condition for a Steiner triple system $\cs$ to be universal.

(2) With the help of this condition we identify an infinite family of universal point-intransitive Steiner triple systems that contain no proper universal subsystem. Only one such system was previously known.

(3) We construct an infinite family of non-universal Steiner triple systems none of which is either projective or affine, disproving a conjecture made by Holroyd and the last author in 2004.

Item Type: Journal Item
Copyright Holders: 2012 Wiley Periodicals, Inc.
ISSN: 1097-0118
Keywords: edge-coloring; Steiner triple system; cubic graph
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 39211
Depositing User: Mike Grannell
Date Deposited: 06 Jan 2014 13:49
Last Modified: 01 May 2019 11:38
URI: http://oro.open.ac.uk/id/eprint/39211
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU