tailieunhanh - Báo cáo toán học: "On the upper and lower chromatic numbers of BSQSs(16)"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: On the upper and lower chromatic numbers of BSQSs(16). | On the upper and lower chromatic numbers of BSQSs 16 Giovanni Lo Faro Department of Mathematics University of Messina Salita Sperone 31 - 98166 Sant Agata - Messina Italy. E-mail lofaro@ Lorenzo Milazzo Department of Mathematics University of Catania Viale A. Doria 6 95125 - Catania Italy. E-mail milazzo@ Antoinette Tripodi Department of Mathematics University of Messina Salita Sperone 31 - 98166 Sant Agata - Messina Italy. E-mail tripodi@ Submitted September 6 1999 Accepted October 20 2000 Abstract A mixed hypergraph is characterized by the fact that it possesses C-edges as well as P-edges. In a colouring of a mixed hypergraph every C-edge has at least two vertices of the same colour and every P-edge has at least two vertices coloured differently. The upper and lower chromatic numbers X X are the maximum and minimum numbers of colours for which there exists a colouring using all the colours. The concepts of mixed hypergraph upper and lower chromatic numbers are applied to SQSs. In fact a BSQS is an SQS where all the blocks are at the same time C-edges and P-edges. In this paper we prove that any BSQS 16 is colourable with the upper chromatic number X 3 and we give new information about the chromatic spectrum of BSQSs 16 . Supported by cofin. MURST Strutture geometriche combinatorie e loro applicazioni and by . . . THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R6 1 1 Introduction A mixed hypergraph 11 12 is a triple H X C D where X is a finite set of vertices while C and D are two families of subsets of X. The elements of C and D are called C-edges and D-edges respectively. If C 0 then H is called a D-hypergraph while if D 0 then H is called a C-hypergraph. A strict k-colouring of H is a vertex colouring where any C-edge has at least two vertices of the same colour and any D-edge has at least two vertices coloured differently and exactly k colours are used in it. If it is not necessary to know the number