Colouring cubic graphs by small Steiner triple systems

被引:2
|
作者
Pal, David
Skoviera, Martin
机构
[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
[2] Comenius Univ, Dept Comp Sci, Fac Math Phys & Informat, Bratislava 84248, Slovakia
关键词
cubic graph; edge-colouring; Steiner triple system;
D O I
10.1007/s00373-007-0696-1
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a Steiner triple system S, we say that a cubic graph G is S-colourable if its edges can be coloured by points of S in such way that the colours of any three edges meeting at a vertex form a triple of S. We prove that there is Steiner triple system U of order 21 which is universal in the sense that every simple cubic graph is U-colourable. This improves the result of Grannell et al. [J. Graph Theory 46 (2004), 15-24] who found a similar system of order 381. On the other hand, it is known that any universal Steiner triple system must have order at least 13, and it has been conjectured that this bound is sharp (Holroyd and. Skoviera [J. Combin. Theory Ser. B 91 (2004), 57-66]).
引用
收藏
页码:217 / 228
页数:12
相关论文
共 50 条
  • [41] Watermark design based on Steiner triple systems
    Yang, Zhi-Fang
    Chiou, Shyh-Shin
    Lee, Jun-Ting
    MULTIMEDIA TOOLS AND APPLICATIONS, 2014, 72 (03) : 2177 - 2194
  • [42] On 6-sparse Steiner triple systems
    Forbes, A. D.
    Grannell, M. J.
    Griggs, T. S.
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2007, 114 (02) : 235 - 252
  • [43] Egalitarian Steiner triple systems for data popularity
    Charles J. Colbourn
    Designs, Codes and Cryptography, 2021, 89 : 2373 - 2395
  • [44] Watermark design based on Steiner triple systems
    Zhi-Fang Yang
    Shyh-Shin Chiou
    Jun-Ting Lee
    Multimedia Tools and Applications, 2014, 72 : 2177 - 2194
  • [45] Steiner triple systems with disjoint or intersecting subsystems
    Colbourn, CJ
    Oravas, MA
    Rees, RS
    JOURNAL OF COMBINATORIAL DESIGNS, 2000, 8 (01) : 58 - 77
  • [46] Steiner triple systems with two disjoint subsystems
    Bryant, D
    Horsley, D
    JOURNAL OF COMBINATORIAL DESIGNS, 2006, 14 (01) : 14 - 24
  • [47] Large Sets of Mutually Almost Disjoint Steiner Triple Systems Not from Steiner Quadruple Systems
    Franek F.
    Rosa A.
    Griggs T.S.
    Designs, Codes and Cryptography, 1997, 12 (1) : 59 - 67
  • [48] FROM STEINER TRIPLE SYSTEMS TO 3-SUN SYSTEMS
    Fu, Chin-Mei
    Jhuang, Nan-Hua
    Lin, Yuan-Lung
    Sung, Hsiao-Ming
    TAIWANESE JOURNAL OF MATHEMATICS, 2012, 16 (02): : 531 - 543
  • [50] Steiner triple systems and spreading sets in projective spaces
    Nagy, Zoltan Lorant
    Szemeredi, Levente
    JOURNAL OF COMBINATORIAL DESIGNS, 2022, 30 (08) : 549 - 560