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

Avinandan Das

This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k\ge 1$, a $k$-partial coloring requires t…