×

Upper chromatic number of Steiner triple and quadruple systems. (English) Zbl 0901.05012

A strict colouring of a mixed hypergraph \(H= (V,{\mathcal E},{\mathcal A})\) is a colouring of the elements of \(V\) (vertices) such that no element of \({\mathcal E} \) (edges) is monochromatic, and no element of \({\mathcal A}\) (co-edges, called anti-edges in this paper) is multicoloured. The upper chromatic number of \(H\), \(\overline\chi(H)\), is the maximum number of colours that can occur in a strict colouring of \(H\). A mixed hypergraph without a strict colouring is uncolourable, and its upper chromatic number is defined to be \(0\). It is shown that if \(H\) is a Steiner triple system (in which the blocks are co-edges, or both edges and co-edges at the same time) of order \(v\leq 2^k- 1\) then \(\overline\chi(H)\leq k\). Moreover, if \(v\leq 2^k- 1\) and \(\overline\chi(H)= k\) then \(v= 2^k- 1\), and in any strict colouring of \(H\) with \(k\) colours, the colour classes have cardinalities \(2^0,2^1,\dots, 2^{k- 1}\). When the blocks of the Steiner triple system are both edges and co-edges, there exist infinitely many uncolourable Steiner triple systems. Some observations on strict colourings of Steiner quadruple systems are made as well.

MSC:

05B07 Triple systems
05B05 Combinatorial aspects of block designs
05C65 Hypergraphs

Citations:

Zbl 0901.05013
Full Text: DOI

References:

[1] Barrau, J. A., On the combinatory problems of Steiner, (Kon. Akad. Wetensch. Amst. Proc. Sect. Sci., 11 (1908)), 352-360
[2] Brandes, M.; Rödl, V., Steiner Triple Systems with small maximal independent sets, Ars Combin., 17, 15-19 (1984) · Zbl 0548.51010
[3] Doyen, J.; Vandensavel, M., Non-isomorphic Steiner quadruple systems, Bull. Soc. Math. Belg, 23, 393-410 (1971) · Zbl 0252.05012
[4] Gionfriddo, M.; Lo Faro, G., 2-colourings in \(S(t,t + 1, v)\), Discrete Math., 111, 263-268 (1993) · Zbl 0789.05005
[5] Hanani, H., On quadruple systems, Canad. J. Math., 12, 145-157 (1960) · Zbl 0092.01202
[6] Lindner, C. C.; Rosa, A., Steiner quadruple systems: a survey, Discrete Math., 22, 147-181 (1968) · Zbl 0398.05015
[7] L. Milazzo and Zs. Tuza, Strict colourings of Steiner systems, in preparation.; L. Milazzo and Zs. Tuza, Strict colourings of Steiner systems, in preparation.
[8] Voloshin, V. I., The mixed hypergraphs, Comput. Sci. J. Moldova, 1, 45-52 (1993)
[9] Voloshin, V. I., On the upper chromatic number of a hypergraph, Australasian J. Combin., 11, 25-45 (1995) · Zbl 0827.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.