Upper chromatic number of Steiner triple and quadruple systems (Q1377792): Difference between revisions

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.