Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally

Abstract

We investigate the classical and distributed complexity of \emph{$k$-partial $c$-coloring} where $c=k$, a natural generalization of Brooks' theorem where each vertex should be colored from the palette $\{1,\dots ,c\}=\{1,\dots ,k\}$ such that it must have at least $\min \{k,\hat{A}°(v)\}$ neighbors colored differently. Das, Fraigniaud, and Ros{é}n~[OPODIS 2023] showed that the problem of $k$-partial $(k+1)$-coloring admits efficient centralized and distributed algorithms and posed an open problem about the status of the distributed complexity of $k$-partial $k$-coloring. We show that the problem becomes significantly harder when the number of colors is reduced from $k+1$ to $k$ for every constant $k\ge 3$. In the classical setting, we prove that deciding whether a graph admits a $k$-partial $k$-coloring is NP-complete for every constant $k\ge 3$, revealing a sharp contrast with the linear-time solvable $(k+1)$-color case. For the distributed LOCAL model, we establish an $\hat{I}\text{c◯}(n)$-round lower bound for computing $k$-partial $k$-colorings, even when the graph is guaranteed to be $k$-partial $k$-colorable. This demonstrates an exponential separation from the $O({\log }^{2}k\cdot \log n)$-round algorithms known for $(k+1)$-colorings. Our results leverage novel structural characterizations of ``hard instances'' where partial coloring reduces to proper coloring, and we construct intricate graph gadgets to prove lower bounds via indistinguishability arguments.