REVIEW 2 cited by
Faster 3-colouring algorithm for graphs of diameter 3
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Faster 3-colouring algorithm for graphs of diameter 3
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].
Forward citations
Cited by 2 Pith papers
-
List $3$-coloring $C_4$-free graphs of diameter-$2$ in polynomial-time
Polynomial-time algorithm for list 3-coloring C4-free diameter-2 graphs via structural characterization of non-3-colorable instances.
-
List $3$-coloring $C_4$-free graphs of diameter-$2$ in polynomial-time
List 3-coloring of C4-free diameter-2 graphs is solvable in polynomial time using a structural characterization of non-3-colorable instances.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.