Library
Repository Home account_circle Login

Faster 3-Colouring Algorithm for Graphs of Diameter 3

Conference Paper (2026)
Author(s)

Carla Groenland (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Hidde Koerts (University of Waterloo)

Sophie Spirkl (University of Waterloo)

Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.4230/LIPIcs.WG.2026.19 Final published version
More Info
expand_more
Publication Year
2026
Language
English
Research Group
Discrete Mathematics and Optimization
Article number
19
Publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (electronic)
9783959774307
Event
52nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2026 (2026-06-02 - 2026-06-04), Kortrijk, Belgium
Page Views
36
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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ębski, Piecyk and Rzążewski [Faster 3-coloring of small-diameter graphs, ESA 2021].