A Steiner triple system which colors all cubic graphs |
| |
Authors: | Mike Grannell Terry Griggs Martin Knor Martin koviera |
| |
Institution: | Mike Grannell,Terry Griggs,Martin Knor,Martin Škoviera |
| |
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 |
| |
Keywords: | cubic graphs coloring Steiner triple system |
|