@inproceedings{c7b4d11c089a4e4f8047cf44955d0745,
title = "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 2O(n2/3−ε) for any ε < 1/33. This improves on the previous best algorithm of 2O((n log n)2/3) from D{\c e}bski, Piecyk and Rz{\c a}{\.z}ewski [Faster 3-coloring of small-diameter graphs, ESA 2021].",
keywords = "3-colouring, diameter-3 graphs, subexponential-time algorithm",
author = "Carla Groenland and Hidde Koerts and Sophie Spirkl",
year = "2026",
doi = "10.4230/LIPIcs.WG.2026.19",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Jan Goedgebeur and Pawel Rzazewsk",
booktitle = "52nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2026",
address = "Germany",
note = "52nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2026 ; Conference date: 02-06-2026 Through 04-06-2026",
}