*********************************** * 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)