Faster 3-colouring algorithm for graphs of diameter 3

Abstract

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-\epsilon })}$ for any $\epsilon <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].

Corrected typos and revised the proof of Claim 7.4