Faster 3-colouring algorithm for graphs of diameter 3
arXiv:2601.1307221.5h-index: 4
Predicted impact top 55% in CO · last 90 daysOriginality Synthesis-oriented
AI Analysis
For researchers in graph algorithms, this provides a concrete improvement in the exponent for a specific graph class, though the improvement is incremental.
The paper presents a faster algorithm for deciding 3-colourability in graphs of diameter 3, achieving time complexity 2^{O(n^{2/3-ε})} for any ε < 1/33, improving over the previous best of 2^{O((n log n)^{2/3})}.
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].