A bicoloring of a Steiner triple system STS(n) on n vertices is a coloring of vertices in such a way that every block receives precisely two colors. The maximum (resp. minimum) number of colors in a bicoloring of an STS(n) is denoted by χ¯¯¯ (resp. χ). All bicolorable STS(2h−1)s have upper chromatic number χ¯¯¯≤h; also, if χ¯¯¯=h<10, then lower and upper chromatic numbers coincide, namely, χ=χ¯¯¯=h. In 2003, M. Gionfriddo conjectured that this equality holds whenever χ¯¯¯=h≥2. In this paper we discuss some extensions of bicolorings of STS(v) to bicoloring of STS(2v+1) obtained by using the ‘doubling plus one construction’. We prove several necessary conditions for bicolorings of STS(2v+1) provided that no new color is used. In addition, for any natural number h we determine a triple system STS(2h+1−1) which admits no extended bicolorings.

Extending bicolorings of Steiner triple system of order 2^h-1

GIONFRIDDO, Mario;GUARDO, ELENA MARIA;MILAZZO, Lorenzo Maria Filippo;
2017-01-01

Abstract

A bicoloring of a Steiner triple system STS(n) on n vertices is a coloring of vertices in such a way that every block receives precisely two colors. The maximum (resp. minimum) number of colors in a bicoloring of an STS(n) is denoted by χ¯¯¯ (resp. χ). All bicolorable STS(2h−1)s have upper chromatic number χ¯¯¯≤h; also, if χ¯¯¯=h<10, then lower and upper chromatic numbers coincide, namely, χ=χ¯¯¯=h. In 2003, M. Gionfriddo conjectured that this equality holds whenever χ¯¯¯=h≥2. In this paper we discuss some extensions of bicolorings of STS(v) to bicoloring of STS(2v+1) obtained by using the ‘doubling plus one construction’. We prove several necessary conditions for bicolorings of STS(2v+1) provided that no new color is used. In addition, for any natural number h we determine a triple system STS(2h+1−1) which admits no extended bicolorings.
2017
coloring, Steiner triple system; mixed hypergraph
File in questo prodotto:
File Dimensione Formato  
BGGMTV-SS-1.pdf

accesso aperto

Licenza: Non specificato
Dimensione 123.39 kB
Formato Adobe PDF
123.39 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/19438
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact