3-colouring diameter-2 graphs quasi-polynomial time

Status open high confidence

Problem 1 of arXiv:2601.13072 asks whether 3-colouring can be solved on diameter-2 graphs in quasi-polynomial time; this is highlighted by the authors as an explicit intermediate target toward polynomial-time solvability, which they call the most intriguing open problem in the area. The best known algorithm for diameter-2 graphs remains the subexponential 2^O(sqrt(n log n)) bound of Mertzios and Spirakis, with no improvement found since the paper's posting. A wide web search conducted in May 2026 returned no follow-up paper addressing the quasi-polynomial or polynomial solvability of 3-colouring on diameter-2 graphs.

Reviewer notes. The conjecture was posed in January 2026 and is less than 6 months old at review time. No follow-up resolving it was found in the indexed literature. The related paper arXiv:2511.09707 achieves quasi-polynomial time for 3-colouring circle graphs (n^O(log n)), but that is a different graph class. The notorious open status of diameter-2 3-colouring is attributed to Paulusma's survey of the area; the source paper itself introduces the quasi-polynomial intermediate target explicitly.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).