Colouring the 1-skeleton of d-dimensional triangulations

2024/09/18 by Tim Planken, Planken, Tim
Computer Science · #05C10 (Secondary) #05C15 (Primary) #05E45 #Advanced Graph Theory Research #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2409.11762

openalex publication_date 2024/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

While every plane triangulation is colourable with three or four colours, Heawood showed that a plane triangulation is 3-colourable if and only if every vertex has even degree. In d ≥ 3 dimensions, however, every k ≥ d+1 may occur as the chromatic number of some triangulation of \mathbb S^d. As a first step, Joswig structurally characterised which triangulations of \mathbb S^d have a (d+1)-colourable 1-skeleton. In the 20 years since Joswig's result, no characterisations have been found for any k>d+1. In this paper, we structurally characterise which triangulations of \mathbb S^d have a (d+2)-colourable 1-skeleton: they are precisely the triangulations that have a subdivision such that for every (d-2)-cell, the number of incident (d-1)-cells is divisible by three.

Related

• A characterisation of 3-colourable 3-dimensional triangulations
• Three-color graph as the 1-skeleton of the 2-sphere triangulation
• Towards a classical proof of the 4-colour theorem
• Enumeration of plane triangulations with all vertices of degree 3 or 6 and a new characterization of akempic triangulations
• Deciding 4-colorability of planar triangulations