{"ID":2879416,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.16308","arxiv_id":"2508.16308","title":"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,\\ldots,c\\} = \\{1,\\ldots,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\\geq 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 \\geq 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(\\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.","short_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,\\ldots,c\\} = \\{1,\\ldots,k\\}$ such that it must have at least $\\min\\{k, °(v)\\}$ neighbors colored differently. Das,...","url_abs":"https://arxiv.org/abs/2508.16308","url_pdf":"https://arxiv.org/pdf/2508.16308v1","authors":"[\"Jan Bok\",\"Avinandan Das\",\"Anna Gujgiczer\",\"Nikola Jedličková\"]","published":"2025-08-22T11:33:34Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.CC\",\"cs.DM\"]","methods":"[\"LoRA\"]","has_code":false}