A square coloring of a graph $G$ is a coloring of the square ${G}^{2}$ 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 ${n}^{{2}^{\mathrm{tw}+4}+O(1)}$ for graphs of treewidth at most $\mathrm{tw}$ . The somewhat
unusual exponent ${2}^{\mathrm{tw}}$ in the running time is essentially
optimal: we show that for any $\u03f5>0$ , there is no algorithm with running
time $f(\mathrm{tw}){n}^{(2-\u03f5{)}^{\mathrm{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\ge 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 ${2}^{O({n}^{2/3}\mathrm{log}n)}$ on planar graphs. The
result follows from the combination of two algorithms. If the number $q$ of
colors is small ($\le {n}^{1/3}$ ), then we can exploit a treewidth bound on the
square of the graph to solve the problem in time ${2}^{O(\sqrt{qn}\mathrm{log}n)}$ . If
the number of colors is large ($\ge {n}^{1/3}$ ), then an algorithm based on
protrusion decompositions and building on our result for the bounded-treewidth
case solves the problem in time ${2}^{O(n\mathrm{log}n/q)}$ .

PREPRINT

# Computing Square Colorings on Bounded-Treewidth and Planar Graphs

Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek

Submitted on 8 November 2022

## Abstract

## Preprint

Comment: 72 pages, 15 figures, full version of a paper accepted at SODA 2023

Subjects: Computer Science - Data Structures and Algorithms; Computer Science - Discrete Mathematics