After the Biwheel: The Largest Four-Colouring Counts of Planar Triangulations

Let P₄(T) count proper vertex colourings with four labelled colours of a simple sphere triangulation T on N vertices. We determine the ten largest distinct four-colouring counts, including every attaining graph: ranks one to four for N ≥ 9, five to eight for N ≥ 13, and nine and ten for N ≥ 17. An eight-extension diamond gives a counterexample to a step in Seymour's proof of the biwheel maximum. Degree-four and degree-five identities yield an independent proof and a sharp non-biwheel bound. They also describe every triangulation near the top of the colouring spectrum: for at least thirteen vertices, a triangulation with more than (5/16)·2ᴺ + 144 + 16(−1)ᴺ colourings lies in one of three explicit four-connected families, is a biwheel with one added vertex of degree three, or is a face-gluing of two biwheels. Closed counting formulas then reduce every ranking above this level to elementary maximization. A further consequence is the bound P₄(T) ≤ (15/64)·2ᴺ for minimum degree at least five, strengthened to (3/64)·2ᴺ in the presence of a separating triangle. The extremal proofs do not depend on enumeration; finite computations and circle-packing figures illustrate the results.

Authors

Publication Details

Journal
Figshare
Published
2026-10-28
DOI
https://doi.org/10.6084/m9.figshare.34842666
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

After the Biwheel: The Largest Four-Colouring Counts of Planar Triangulations

Anton Joha
Figshare
Advanced Graph Theory Research
preprint

After the Biwheel: The Largest Four-Colouring Counts of Planar Triangulations

Anton Joha
preprint en

Abstract

Let P₄(T) count proper vertex colourings with four labelled colours of a simple sphere triangulation T on N vertices. We determine the ten largest distinct four-colouring counts, including every attaining graph: ranks one to four for N ≥ 9, five to eight for N ≥ 13, and nine and ten for N ≥ 17. An eight-extension diamond gives a counterexample to a step in Seymour's proof of the biwheel maximum. Degree-four and degree-five identities yield an independent proof and a sharp non-biwheel bound. They also describe every triangulation near the top of the colouring spectrum: for at least thirteen vertices, a triangulation with more than (5/16)·2ᴺ + 144 + 16(−1)ᴺ colourings lies in one of three explicit four-connected families, is a biwheel with one added vertex of degree three, or is a face-gluing of two biwheels. Closed counting formulas then reduce every ranking above this level to elementary maximization. A further consequence is the bound P₄(T) ≤ (15/64)·2ᴺ for minimum degree at least five, strengthened to (3/64)·2ᴺ in the presence of a separating triangle. The extremal proofs do not depend on enumeration; finite computations and circle-packing figures illustrate the results.

Figshare
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