Premium
A Steiner triple system which colors all cubic graphs
Author(s) -
Grannell Mike,
Griggs Terry,
Knor Martin,
Škoviera Martin
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10166
Subject(s) - combinatorics , cubic graph , mathematics , vertex (graph theory) , graph , steiner system , edge coloring , discrete mathematics , order (exchange) , line graph , graph power , voltage graph , finance , economics
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