✦ LIBER ✦
A Steiner triple system which colors all cubic graphs
✍ Scribed by Mike Grannell; Terry Griggs; Martin Knor; Martin Škoviera
- Publisher
- John Wiley and Sons
- Year
- 2004
- Tongue
- English
- Weight
- 93 KB
- Volume
- 46
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 15–24, 2004