One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming

This paper investigates the semi-streaming complexity of $k\mathit{\text{-partial}}\mathit{\text{coloring}}$, a generalization of proper graph coloring. For $k\ge 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,\mathrm{°}(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 $(\mathrm{\Delta }+1)$-proper coloring and $\mathrm{\Delta }$-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA~2019] and Assadi, Kumar, and Mittal [TheoretiCS~2023] show that both $(\mathrm{\Delta }+1)$-proper coloring and $\mathrm{\Delta }$-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.