2026-08-03T06:15:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14618 2024-03-06T10:54:27Z ddc:004 open_access

Faster 3-Coloring of Small-Diameter Graphs Dębski, Michał Piecyk, Marta Rzążewski, Paweł 3-coloring fine-grained complexity subexponential-time algorithm diameter We study the 3-Coloring problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponential time 2^{𝒪(√{n log n})}. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graphs theory. In this paper we present an algorithm that solves 3-Coloring in n-vertex diameter-2 graphs in time 2^{𝒪(n^{1/3} log² n)}. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition to standard branchings and reducing the problem to an instance of 2-Sat, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3-Coloring can be solved in time 2^{𝒪((n log n)^{2/3})} in n-vertex diameter-3 graphs. We also generalize our algorithms to the problem of finding a list homomorphism from a small-diameter graph to a cycle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michał Dębski and Marta Piecyk and Paweł Rzążewski 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.37 urn:nbn:de:0030-drops-146181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.37 eng https://creativecommons.org/licenses/by/4.0/legalcode