DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.19

Faster 3-Colouring Algorithm for Graphs of Diameter 3

Authors: Carla Groenland, Hidde Koerts, and Sophie Spirkl

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

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-ε})} for any ε < 1/33. This improves on the previous best algorithm of 2^{O((nlog n)^{2/3})} from Dębski, Piecyk and Rzążewski [Faster 3-coloring of small-diameter graphs, ESA 2021].

Cite as

Carla Groenland, Hidde Koerts, and Sophie Spirkl. Faster 3-Colouring Algorithm for Graphs of Diameter 3. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.WG.2026.19,
  author =	{Groenland, Carla and Koerts, Hidde and Spirkl, Sophie},
  title =	{{Faster 3-Colouring Algorithm for Graphs of Diameter 3}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.19},
  URN =		{urn:nbn:de:0030-drops-261851},
  doi =		{10.4230/LIPIcs.WG.2026.19},
  annote =	{Keywords: 3-colouring, subexponential-time algorithm, diameter-3 graphs}
}

Search Results

Documents authored by Koerts, Hidde

Faster 3-Colouring Algorithm for Graphs of Diameter 3

Abstract

Cite as

Thanks for your feedback!

Could not send message