An explicit 92-colouring of DIMACS latin_square_10
The graph latin_square_10, with 900 vertices and 307,350 edges, has been a graph-colouring benchmark since the Second DIMACS Implementation Challenge. Its chromatic number is at least 90. Published heuristic results include Lewandowski and Condon’s 109 colours in their February 1994 report, Morgenstern’s 98 (documented in November 1994 and published in 1996), and Titiloye and Crispin’s 97 in 2011. Goudet, Grelier and Hao (2022) and Schidler and Szeider (2023) still list 97 as the best known value. In this paper we give an explicit proper 92-colouring, built from the four incomplete mutually orthogonal Latin squares of order 10 with a hole of order 2 that Brouwer published in 1984. A normalization of the associated 98-word code yields 88 disjoint independent sets of size 10, and four further classes of sizes 6, 6, 4 and 4 complete the colouring. The design and the existence of the code are established results; what is recorded here is their consequence for the benchmark. A certificate in the original DIMACS vertex numbering accompanies the paper, with a standalone verifier that checks every edge.
Authors
- Olawale Titiloye (ORCID: https://orcid.org/0009-0007-7623-7169)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.5281/zenodo.24267440
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint