{"id":"arxiv/2601.13072","url":"https://arxiv.org/abs/2601.13072","tags":["math.CO","cs.DM"],"score":0,"title":"Faster 3-colouring algorithm for graphs of diameter 3","domain":"math.CO","source":"arxiv","authors":["Carla Groenland","Hidde Koerts","Sophie Spirkl"],"reviews":0,"subject":"math.CO","summary":"We show that given an $n$-vertex graph $G$ of diameter 3 we can decide if $G$ is $3$-colourable in time $2^{O(n^{2/3-\\varepsilon})}$ for any $\\varepsilon < 1/33$. This improves on the previous best algorithm of $2^{O((n\\log n)^{2/3})}$ from Dębski, Piecyk and Rzążewski [Faster 3-coloring of small-diameter graphs, ESA 2021].","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-19","reactions":{}}