pith. sign in

arxiv: 2601.13072 · v2 · pith:WNI2TDAPnew · submitted 2026-01-19 · 🧮 math.CO · cs.DM

Faster 3-colouring algorithm for graphs of diameter 3

classification 🧮 math.CO cs.DM
keywords algorithmdiameterfastergraphsvarepsilonbestbskicoloring
0
0 comments X
read the original 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-\varepsilon})}$ for any $\varepsilon < 1/33$. This improves on the previous best algorithm of $2^{O((n\log n)^{2/3})}$ from D\k{e}bski, Piecyk and Rz\k{a}\.zewski [Faster 3-coloring of small-diameter graphs, ESA 2021].

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.