Six-chromatic two-distance graphs on 26 and 30 vertices

Two explicit vertex-critical six-chromatic two-distance graphs in the Euclidean plane. A two-distance graph joins two points exactly when their distance is one of two prescribed values; other pairwise distances are unrestricted. S26 has 26 vertices and 84 edges at the lengths 1 and sqrt(2+sqrt3). H30 has 30 vertices and 99 edges at the lengths 1 and sqrt3. The smallest six-chromatic two-distance graph previously recorded in the literature we have located is the 31-vertex example of Parts (Geombinatorics 29(3), 2020, 111-115), so to the best of our knowledge 26 is the smallest order reached so far, across all distance ratios. No lower bound on the order is claimed, and no uniqueness. The two graphs improve the 117-vertex and 33-vertex constructions of De Neve, Vanden Kerchove, Colle, Tavernier and Pickavet (American Mathematical Monthly 132(10), 2025, 1007-1022) at the corresponding ratios. Both are vertex-critical: deleting any single vertex leaves a five-colourable graph. Coordinates are exact, lying in Q(sqrt3,sqrt7) and Q(sqrt3,sqrt5). For S26 the independence number is 5, so five colour classes cover at most 25 of the 26 vertices and six colours are forced by counting alone. For H30 the independence number is 6, and the lower bound instead comes from a checked refutation of the five-colouring formula. This deposit contains the manuscript and a verification archive: two programs that use only the Python standard library and exact integer arithmetic, and that decide every claim of the main theorem directly from the coordinate tables printed in the paper, with no SAT solver and no floating point. Preprint, not peer reviewed. Submitted to the Australasian Journal of Combinatorics.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24227219
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Six-chromatic two-distance graphs on 26 and 30 vertices

Chandan Shukla
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Six-chromatic two-distance graphs on 26 and 30 vertices

Chandan Shukla
preprint en

Abstract

Two explicit vertex-critical six-chromatic two-distance graphs in the Euclidean plane. A two-distance graph joins two points exactly when their distance is one of two prescribed values; other pairwise distances are unrestricted. S26 has 26 vertices and 84 edges at the lengths 1 and sqrt(2+sqrt3). H30 has 30 vertices and 99 edges at the lengths 1 and sqrt3. The smallest six-chromatic two-distance graph previously recorded in the literature we have located is the 31-vertex example of Parts (Geombinatorics 29(3), 2020, 111-115), so to the best of our knowledge 26 is the smallest order reached so far, across all distance ratios. No lower bound on the order is claimed, and no uniqueness. The two graphs improve the 117-vertex and 33-vertex constructions of De Neve, Vanden Kerchove, Colle, Tavernier and Pickavet (American Mathematical Monthly 132(10), 2025, 1007-1022) at the corresponding ratios. Both are vertex-critical: deleting any single vertex leaves a five-colourable graph. Coordinates are exact, lying in Q(sqrt3,sqrt7) and Q(sqrt3,sqrt5). For S26 the independence number is 5, so five colour classes cover at most 25 of the 26 vertices and six colours are forced by counting alone. For H30 the independence number is 6, and the lower bound instead comes from a checked refutation of the five-colouring formula. This deposit contains the manuscript and a verification archive: two programs that use only the Python standard library and exact integer arithmetic, and that decide every claim of the main theorem directly from the coordinate tables printed in the paper, with no SAT solver and no floating point. Preprint, not peer reviewed. Submitted to the Australasian Journal of Combinatorics.

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