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
- Anton Joha (ORCID: https://orcid.org/0000-0002-1215-5638)
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