tailieunhanh - Báo cáo toán học: "Bicoloring Steiner Triple Systems"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Bicoloring Steiner Triple Systems. | Bicoloring Steiner Triple Systems Charles J. Colbourn Computer Science University of Vermont Burlington VT 05405 colbourn@ Jeffrey H. Dinitz Mathematics and Statistics University of Vermont Burlington VT 05405 Alexander Rosa Mathematics and Statistics McMaster University Hamilton Ontario Canada L8S 4K1 rosa@ Submitted March 31 1999 Accepted May 24 1999. Abstract A Steiner triple system has a bicoloring with m color classes if the points are partitioned into m subsets and the three points in every block are contained in exactly two of the color classes. In this paper we give necessary conditions for the existence of a bicoloring with 3 color classes and give a multiplication theorem for Steiner triple systems with 3 color classes. We also examine bicolorings with more than 3 color classes. Math Subject Clasification 05B07 1 Introduction Throughout this paper we use notation consistent with that found in 2 . Let D V B be a v k A -design. A coloring of D is a mapping V C. The elements of C are colors if CI m we have an m-coloring of D. For 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R25 2 each c 2 C the set -1 c x x cg is a color class. A coloring of D is weak strong if for all B 2 B I B 1 B k respectively where B Uv2B v . Each color class in a weak or strong coloring is an independent set. In a weak coloring no block is monochromatic . no block has all its elements the same color while in a strong coloring the elements of any block B get I B I distinct colors. The weak strong chromatic number of D is the smallest m for which D admits a weak strong m-coloring. Much work has been done on weak and strong colorings for an extensive survey of these results the reader is referred to 9 . For triple systems the following results concerning weak colorings are known. Theorem 3 . For every admissible v 5 and any X there exists a weakly 3-chromatic 2 v 3 X -design. A modihcation of Bose s and Skolem s .