Upper chromatic number of Steiner triple and quadruple systems
type: Item
instance of: scholarly article
title: Upper chromatic number of Steiner triple and quadruple systems
zbMATH Open document ID: 0901.05012
DOI: 10.1016/S0012-365X(97)80332-9
author: Lorenzo Milazzo
author: Zsolt Tuza
published in: Discrete Mathematics
publication date: 1998-11-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B07
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1110050
zbMATH Keywords: strict colouring
zbMATH Keywords: mixed hypergraph
zbMATH Keywords: upper chromatic number
zbMATH Keywords: Steiner triple system
zbMATH Keywords: Steiner quadruple systems
reviewed by: Alexander Rosa
MaRDI profile type: Publication
cites work: Q3339657
cites work: Q5665204
cites work: 2-colourings in \(S(t, t+1, v)\)
cites work: On Quadruple Systems
cites work: Steiner quadruple systems - a survey
cites work: Q4842710
Recommended article: Strict colorings of Steiner triple and quadruple systems: A survey
Recommended article: Q4867928
Recommended article: Q5421117
Recommended article: Lower and upper chromatic numbers for BSTSs\((2^h-1)\)
Recommended article: A primal-dual property of the upper chromatic number of mixed hypergraphs
Recommended article: Q5503319
Recommended article: Chromatic spectrum is broken
Recommended article: The chromatic spectrum of mixed hypergraphs
Recommended article: Strict colouring for classes of Steiner triple systems
Recommended article: Strict colourings for classes of 4-cycle systems
description: scientific article; zbMATH DE number 1110050