Bicolouring Steiner systems \(S\)(2,4,\(v\))
type: Item
instance of: scholarly article
title: Bicolouring Steiner systems \(S\)(2,4,\(v\))
zbMATH Open document ID: 1044.05018
author: Mario Gionfriddo
author: Lorenzo Milazzo
author: Alexander Rosa
author: V. I. Voloshin
published in: Discrete Mathematics
publication date: 2004-08-06T00:00:00Z
review text: A colouring of an \(S(2,4,v)\) is a bicolouring if each block is coloured with precisely two colours. An \(S(2,4,v)\) is bicolourable if it admits at least one bicolouring. A bicolouring using exactly \(h\) colours is an \(h\)-bicolouring. The maximum (respectively minimum) number of colours for which there exists a bicolouring of an \(S(2,4,v)\) is its upper (resp. lower) chromatic number. The authors use \(\bar{{\mathcal X}}_{bi}(v)\) (resp. \({\mathcal X}_{bi}(v)\)) to denote the maximum (resp. minimum) upper (resp. lower) chromatic number taken over all \(S(2,4,v)\)s of order \(v\). The numbers \(\bar{{\mathcal X}}_{bi}(v)\), \({\mathcal X}_{bi}(v)\) are well defined, since for every admissible order \(v \equiv 1,4 \pmod{12}\) there exists a bicolourable \(S(2,4,v)\). But for individual systems \(S(2,4,v)\) there may not be a bicolouring. In fact \textit{S. Milici, A. Rosa} and \textit{V. Voloshin} [Discrete Math. 240, 145--160 (2001; Zbl 0983.05015)] have shown that there is a constant \(v^*\) such that for all admissible \(v > v^*\) there exists an \(S(2,4,v)\) without a bicolouring. In this paper the authors show that \(v^*\) is at least \(28\) as all \(S(2,4,v)\)s with \(v \leq 25\) are bicolourable. They also establish an upper bound for \(\bar{{\mathcal X}}_{bi}(v)\), viz. that if an \(S(2,4,v)\) admits a bicolouring and \(v \leq ((3^d-1)/2)\, (d \in N)\), then \(\bar{{\mathcal X}}_{bi}(v) \leq \lfloor d/\log_32 \rfloor - 1\). Analysing some small systems, the authors show that an \(S(2,4,v)\) with \(v \in \{13,16,25,28\}\) can only be bicoloured using either two or three colours, so that \(\bar{{\mathcal X}}_{bi}(v)=3\) for these orders. Finally, using the ``\(3v+1\) construction'', which enables us to build an \(S(2,4,3v+1)\) system from an \(S(2,4,v)\) system, they show that there exist systems admitting bicolourings with an arbitrarily large number of colours. In particular, their result is that for every \(v \equiv 4,13 \pmod{36}\), \(v \geq 13\), the…
reviewed by: Peter B. Gibbons
Mathematics Subject Classification ID: 05B05
zbMATH DE Number: 2083736
zbMATH Keywords: Steiner system
zbMATH Keywords: bicolouring
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.016
OpenAlex ID: W2008148950
cites work: Completing the spectrum of 2-chromatic \(S(2,4,v)\)
cites work: Blocking sets in designs with block size 4
cites work: The Steiner systems S(2,4,25) with nontrivial automorphism group
cites work: Q4805428
cites work: Q4205446
cites work: Q4876921
cites work: Upper chromatic number of Steiner triple and quadruple systems
cites work: Colouring Steiner systems with specified block colour patterns
cites work: The complete classification of Steiner systems S(2, 4, 25)
cites work: Q3767351
DOI: 10.1016/J.DISC.2003.11.016
Recommended article: Bicoloring Steiner triple systems
Recommended article: Bicolour graphs of Steiner triple systems
Recommended article: Extended bicolorings of Steiner triple systems of order \(2^{h}-1\)
Recommended article: Steiner systems \(S(2,4,v)\) -- a survey
Recommended article: Q4278760
Recommended article: Colouring Steiner quadruple systems
Recommended article: Bichromatic quadrangulations with Steiner points
Recommended article: Q3594053
Recommended article: A construction for 2-chromatic Steiner quadruple systems
Recommended article: Extending bicolorings for Steiner triple systems
description: scientific article; zbMATH DE number 2083736