Upper chromatic number of Steiner triple and quadruple systems (Q1377792): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q1802137 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Alexander Rosa / rank | |||
Normal rank |
Revision as of 11:02, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper chromatic number of Steiner triple and quadruple systems |
scientific article |
Statements
Upper chromatic number of Steiner triple and quadruple systems (English)
0 references
26 November 1998
0 references
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.
0 references
strict colouring
0 references
mixed hypergraph
0 references
upper chromatic number
0 references
Steiner triple system
0 references
Steiner quadruple systems
0 references