***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Paweł Rzążewski (Warsaw)
Thursday 25th March, 15:00 by Zoom. Zoom link TBA
Title: Faster 3-coloring of graphs with small diameter.
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 obtained as joint work with Michał Dębski, Carla Groenland, and Marta
Piecyk.
----------------------------------
Next week: TBA
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)