On $(n-1)$-bicolorable Steiner triple systems of order $2^n-7$
DOI:
https://doi.org/10.13069/jacodesmath.v14i1.456Keywords:
Steiner triple systems, Independent set, BicoloringAbstract
A Steiner triple system STS of order $v$ is a hypergraph of rank 3, with $v$ vertices and such that every 2-subset of vertices has degree 1. In this paper we construct STS$(2v+7)$ containing subsystems STS of order $v$. This construction allows us to obtain, for any $n\ge 5$, $(n-1)$-bicolorable systems STS$(2^n-7)$ having a maximal independent set of largest cardinality.
Received: 04 May 2026 | Accepted: 18 June 2026
Downloads
References
C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam (1973).
C. Bujtás, M. Gionfriddo, E. Guardo, L. Milazzo, Z. Tuza, and V. Voloshin, Extended bicolorings of Steiner triple systems of order $2^h-1$, Taiwanese J. Math. 21(6) (2017) 1265–1276.
M. Buratti, M. Gionfriddo, L. Milazzo, and V. Voloshin, Lower and upper chromatic numbers for $BSTS(2^h-1)$, Comput. Sci. J. Moldova 9(2) (2001) 259–272.
C. J. Colbourn and J. H. Dinitz, Complete arcs in Steiner triple systems, J. Combin. Theory Ser. A 80(2) (1997) 320–333.
C. J. Colbourn, J. H. Dinitz, and A. Rosa, Bicoloring Steiner triple systems, Electron. J. Combin. 6(1) (1999) Research Paper 25.
C. J. Colbourn and A. Rosa, Triple Systems, Oxford University Press, Oxford (1999).
M. Gionfriddo, E. Guardo, and L. Milazzo, Extending bicolorings for Steiner triple systems, Appl. Anal. Discrete Math. 7(2) (2013) 225–234.
M. Gionfriddo, L. Milazzo, and V. Voloshin, Hypergraphs and Designs, Nova Science Publishers, New York (2014).
C. C. Lindner and C. A. Rodger, Design Theory, 2nd ed., Chapman and Hall/CRC, Boca Raton (2008).
L. Milazzo and Z. Tuza, Upper chromatic number of Steiner triple and quadruple systems, Discrete Math. 174(1--3) (1997) 247–259.
L. Milazzo, Z. Tuza, and V. Voloshin, Strict colorings of Steiner triple and quadruple systems: A survey, Discrete Math. 261(1--3) (2003) 399–411.
A. Rosa, Steiner triple systems and their chromatic number, Acta Fac. Rerum Natur. Univ. Comenian. Math. 24 (1970) 159–174.
N. Sauer and J. Schönheim, Maximal subsets of a given set having no triple in common with a Steiner triple system on the set, Canad. Math. Bull. 12(6) (1969) 777–778.
V. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45–52.
V. I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25–45.
V. I. Voloshin, Introduction to Graph and Hypergraph Theory, Nova Science Publishers, New York (2009).
