Albertson's toroidal colouring conjecture

Status open high confidence

Albertson (1981) asked whether every toroidal graph can be made 4-colourable by deleting at most three vertices (M_1 = 3). An infinite family of toroidal graphs requires exactly three deletions, so the bound cannot be lowered. Thomassen proved the five-colour analogue without invoking the Four Colour Theorem, and Hutchinson–Miller showed that all but O(√(gn)) vertices of an n-vertex genus-g graph can be 4-coloured. As of 2018 both the original conjecture (M_1 = 3 for the torus) and the weaker question asking for any finite bound K remain open.

Cited literature (1)

• survey Open Problems for the Barbados Graph Theory Workshop 2018 (2018)
  Dan Král', Jon Noel (Problem 5) · Workshop open-problems list

  Identifies Albertson's conjecture (every toroidal graph is 4-colourable after deleting at most 3 vertices) as open in 2018, notes an infinite family requiring exactly 3 deletions, and observes that even the weaker question of whether any finite bound K exists remains unresolved.

Reviewer notes. The conjecture is part of Albertson's broader 1981 question (in G. Chartrand et al., eds., Theory and Applications of Graphs, Wiley, p. 609): for each surface S_g, does there exist M_g such that every graph embeddable on S_g has all but M_g vertices 4-colourable? For the torus (g=1), the conjecture is M_1 = 3. This should be distinguished from defective/improper 4-coloring of toroidal graphs: a 2025 preprint (arXiv:2509.15870) studies (d_1,d_2,d_3,d_4)-colourability but does not address vertex deletion and leaves 4-colorability with defect 1 open. Known partial results: Thomassen's 5-colour analogue (without 4CT); Hutchinson–Miller O(√(gn)) bound for 4-colouring; existence of an infinite family requiring exactly 3 deletions (tightness). The Mohar open-problems page (sfu.ca, 1995, verified) and the Barbados 2018 workshop (verified) confirm the problem is open. No post-2008 paper resolving the exact statement was found.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).