STEINER TRIPLE SYSTEMS WITH HIGH CHROMATIC INDEX

被引:6
作者
Bryant, Darryn [1 ]
Colbourn, Charles J. [2 ]
Horsley, Daniel [3 ]
Wanless, Ian M. [3 ]
机构
[1] Univ Queensland, Sch Math & Phys, St Lucia, Qld, Australia
[2] Arizona State Univ, Sch Comp Informat & Decis Syst Engn, Tempe, AZ 85287 USA
[3] Monash Univ, Sch Math Sci, Clayton, Vic, Australia
基金
美国国家科学基金会; 澳大利亚研究理事会;
关键词
Steiner triple system; chromatic index; parallel class; block coloring;
D O I
10.1137/17M1114338
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
It has been conjectured that every Steiner triple system of order v + 7 has chromatic index at most (v + 3)/2 when v equivalent to 3 (mod 6) and at most (v + 5)/2 when v equivalent to 1 (mod 6). Herein, we construct a Steiner triple system of order v with chromatic index at least (v + 3)/2 for each integer v equivalent to 3 (mod 6) such that v >= 15, with four possible exceptions. We further show that the maximum number of disjoint parallel classes in the systems constructed is sublinear in v. Finally, we establish for each order v equivalent to 15 (mod 18) that there are at least v(v2(1/6+0(1))) nonisomorphic Steiner triple systems with chromatic index at least (v + 3)/2 and that some of these systems are cyclic.
引用
收藏
页码:2603 / 2611
页数:9
相关论文
共 26 条