Zoom link:  https://princeton.zoom.us/j/91255216570

Passcode: required

We study the 3-coloring problem in graphs with diameter 2. In 2016, Mertzios and Spirakis showed that this problem can be solved in subexponential time 2^O(sqrt(n log n)). Their algorithm is based on the observation that such a graph has a dominating set D of size roughly sqrt(n). Thus we can guess the coloring of D, and then the problem can be reduced to solving an instance of 2-SAT. Despite many side results about solvability the problem in subclasses of diameter 2-graphs, no real progress in the general case has been done since then. The question whether 3-coloring of diameter-2 graphs can be solved in polynomial time remains one of the notorious open problems in the area. We make some progress in the problem by showing a faster subexponential-time algorithm whose complexity is roughly 2^O(n^1/3). In addition to standard branching and reduction to 2-SAT, the crucial building block 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 of diameter-3 graphs can be solved in time 2^O(n^2/3).

The results are obtain as a joint work with Michał Dębski and Marta Piecyk.