Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909752656658432 |
|---|---|
| author | Bok, Jan Das, Avinandan Gujgiczer, Anna Jedličková, Nikola |
| author_facet | Bok, Jan Das, Avinandan Gujgiczer, Anna Jedličková, Nikola |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally Bok, Jan Das, Avinandan Gujgiczer, Anna Jedličková, Nikola Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics F.2.2; G.2.2 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. |
| title | Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally |
| topic | Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2508.16308 |