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

This paper investigates the semi-streaming complexity of k-partial coloring, a generalization of proper graph coloring. For k ≥ 1, a k-partial coloring requires that each vertex v in an n-node graph is assigned a color such that at least mink, deg (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.