2026-10-01T07:51:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26051 2026-09-23T23:58:57Z ddc:004 open_access

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming Das, Avinandan Graph Coloring Semi-streaming algorithms Lower bounds 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 min{k, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avinandan Das 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.15 urn:nbn:de:0030-drops-260515 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.15 eng https://creativecommons.org/licenses/by/4.0/legalcode