We investigate the classical and distributed complexity of k-partial c-coloring where \(c=k\) , a natural generalization of Brooks’ theorem where each vertex should be colored from the palette \(\{1,\ldots ,c\} = \{1,\ldots ,k\}\) such that it must have at least \(\min \{k, \deg (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 \(\varOmega (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.