A Steiner triple system with a broken chromatic spectrum

A bicoloring of a Steiner triple system colors its points so that every block receives exactly two colors, and the feasible set of the system is the set of integers $k$ for which some bicoloring uses exactly $k$ colors. Mario Gionfriddo conjectured in 2003 that the feasible set of every bicolorable Steiner triple system has no gaps; Tuza and Voloshin listed the question as open in 2008, and Gionfriddo restated the conjecture in 2025. In 2014 Gionfriddo, Guardo, Milazzo and Voloshin left open whether a system of order 39 has feasible set $\{3,5\}$. We give a Steiner triple system of order 39 that has bicolorings with exactly three and exactly five colors but none with exactly four, so the conjecture is false. With their theorem that bicolorings of systems of order 39 use three, four or five colors, its feasible set is $\{3,5\}$. The class sizes of the two bicolorings come from the tables of Colbourn, Dinitz and Rosa. The absence of a four-color bicoloring is proved by computer: a SAT solver's clausal refutation of a direct encoding, checked by DRAT-trim and by a separate unit-propagation checker. This work has not yet been reviewed by experts. The proofs, the search code, the certificate checkers and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-31
DOI
https://doi.org/10.5281/zenodo.23838455
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A Steiner triple system with a broken chromatic spectrum

P. Graham
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

A Steiner triple system with a broken chromatic spectrum

P. Graham
preprint en

Abstract

A bicoloring of a Steiner triple system colors its points so that every block receives exactly two colors, and the feasible set of the system is the set of integers $k$ for which some bicoloring uses exactly $k$ colors. Mario Gionfriddo conjectured in 2003 that the feasible set of every bicolorable Steiner triple system has no gaps; Tuza and Voloshin listed the question as open in 2008, and Gionfriddo restated the conjecture in 2025. In 2014 Gionfriddo, Guardo, Milazzo and Voloshin left open whether a system of order 39 has feasible set $\{3,5\}$. We give a Steiner triple system of order 39 that has bicolorings with exactly three and exactly five colors but none with exactly four, so the conjecture is false. With their theorem that bicolorings of systems of order 39 use three, four or five colors, its feasible set is $\{3,5\}$. The class sizes of the two bicolorings come from the tables of Colbourn, Dinitz and Rosa. The absence of a four-color bicoloring is proved by computer: a SAT solver's clausal refutation of a direct encoding, checked by DRAT-trim and by a separate unit-propagation checker. This work has not yet been reviewed by experts. The proofs, the search code, the certificate checkers and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
A Steiner triple system with a broken chromatic spectrum — P. Graham · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS