2025/08/22 by Bok, Jan, Das, Avinandan, Gujgiczer, Anna +1
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Distributed #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2508.16308
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,…,c\ = \1,…,k\ such that it must have at least min\k, °(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≥ 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 ≥ 3, revealing a sharp contrast with the linear-time solvable (k+1)-color case. For the distributed LOCAL model, we establish an Ω(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(log2 k ⋅ 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.