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.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.