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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

An explicit 92-colouring of DIMACS latin_square_10

Olawale Titiloye
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

An explicit 92-colouring of DIMACS latin_square_10

Olawale Titiloye
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
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