One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910029151469568 |
|---|---|
| author | Das, Avinandan |
| author_facet | Das, Avinandan |
| contents | This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k \geq 1$, a $k$-partial coloring requires that each vertex $v$ in an $n$-node graph is assigned a color such that at least $\min\{k, °(v)\}$ of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, $k$-partial $(k+1)$-coloring and $k$-partial $k$-coloring generalize $(Δ+1)$-proper coloring and $Δ$-proper coloring, respectively.
Prior works of Assadi, Chen, and Khanna [SODA~2019] and Assadi, Kumar, and Mittal [TheoretiCS~2023] show that both $(Δ+1)$-proper coloring and $Δ$-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold : while $k$-partial $(k+1)$-coloring admits a one-pass randomized semi-streaming algorithm, the $k$-partial $k$-coloring remains semi-streaming intractable, effectively demonstrating a ``dichotomy of one color'' in the streaming model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18987 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming Das, Avinandan Data Structures and Algorithms Computational Complexity Discrete Mathematics This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k \geq 1$, a $k$-partial coloring requires that each vertex $v$ in an $n$-node graph is assigned a color such that at least $\min\{k, °(v)\}$ of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, $k$-partial $(k+1)$-coloring and $k$-partial $k$-coloring generalize $(Δ+1)$-proper coloring and $Δ$-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA~2019] and Assadi, Kumar, and Mittal [TheoretiCS~2023] show that both $(Δ+1)$-proper coloring and $Δ$-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold : while $k$-partial $(k+1)$-coloring admits a one-pass randomized semi-streaming algorithm, the $k$-partial $k$-coloring remains semi-streaming intractable, effectively demonstrating a ``dichotomy of one color'' in the streaming model. |
| title | One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2602.18987 |