Computing Square Colorings on Bounded-Treewidth and Planar Graphs

A square coloring of a graph G is a coloring of the square G2 of G, that is, a coloring of the vertices of G such that any two vertices that are at distance at most 2 in G receive different colors. We investigate the complexity of finding a square coloring with a given number of q colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time for graphs of treewidth at most tw. The somewhat unusual exponent 2tw in the running time is essentially optimal: we show that for any ε > 0, there is no algorithm with running time f (tw)n(2-ε)tw unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number q ≥ 4 of colors. Our main algorithmic result is showing that the problem (when the number of colors q is part of the input) can be solved in subexponential time on planar graphs. The result follows from the combination of two algorithms. If the number q of colors is small (≤ n1/3), then we can exploit a treewidth bound on the square of the graph to solve the problem in time . If the number of colors is large (≥ n1/3), then an algorithm based on protrusion decompositions and building on our result for the bounded- treewidth case solves the problem in time . * The full version of the paper can be accessed at https://arxiv.org/abs/2211.04458. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.