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 条
  • [21] Embedding hypertrees into steiner triple systems
    Elliott, Bradley
    Rodl, Vojtech
    JOURNAL OF COMBINATORIAL DESIGNS, 2019, 27 (02) : 82 - 105
  • [22] ENUMERATION OF STEINER TRIPLE SYSTEMS WITH SUBSYSTEMS
    Kaski, Petteri
    Ostergard, Patric R. J.
    Popa, Alexandru
    MATHEMATICS OF COMPUTATION, 2015, 84 (296) : 3051 - 3067
  • [23] Orientable biembeddings of cyclic Steiner triple systems from current assignments on Mobius ladder graphs
    Grannell, M. J.
    Korzhik, V. P.
    DISCRETE MATHEMATICS, 2009, 309 (09) : 2847 - 2860
  • [24] Cancellative hypergraphs and Steiner triple systems
    Liu, Xizhi
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 167 : 303 - 337
  • [25] Rigid Steiner Triple Systems Obtained from Projective Triple Systems
    Grannell, M. J.
    Knor, M.
    JOURNAL OF COMBINATORIAL DESIGNS, 2014, 22 (07) : 279 - 290
  • [26] L∞ NORM MINIMIZATION FOR NOWHERE-ZERO INTEGER EIGENVECTORS OF THE BLOCK GRAPHS OF STEINER TRIPLE SYSTEMS AND JOHNSON GRAPHS
    Bespalov, Evgeny Andreevich
    Mogilnykh, Ivan Yurevich
    Vorob'ev, Konstantin Vasil'evich
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2023, 20 (02): : 1125 - 1149
  • [27] Automorphism groups of Steiner triple systems
    Doyen, Jean
    Kantor, William M.
    ALGEBRAIC COMBINATORICS, 2022, 5 (04): : 593 - 608
  • [28] Maximum genus embeddings of Steiner triple systems
    Grannell, MJ
    Griggs, TS
    Sirán, J
    EUROPEAN JOURNAL OF COMBINATORICS, 2005, 26 (3-4) : 401 - 416
  • [29] Steiner triple systems of order 15 and their codes
    Tonchev, VD
    Weishaar, RS
    JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 1997, 58 (01) : 207 - 216
  • [30] STEINER TRIPLE SYSTEMS WITH HIGH CHROMATIC INDEX
    Bryant, Darryn
    Colbourn, Charles J.
    Horsley, Daniel
    Wanless, Ian M.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (04) : 2603 - 2611