Canadian Mathematical Society
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs

Open Access article
 Printed: Apr 2010
  • Daniel Král'
  • Edita Máčajová
  • Attila Pór
  • Jean-Sébastien Sereni
Format:   HTML   LaTeX   MathJax  


It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration $C_{14}$. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations. Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective non-affine point-transitive Steiner triple system S.
MSC Classifications: 05B07, 05C15 show english descriptions Triple systems
Coloring of graphs and hypergraphs
05B07 - Triple systems
05C15 - Coloring of graphs and hypergraphs

© Canadian Mathematical Society, 2018 :