Improved Space Bounds for Promise Graph Coloring in Adversarial Streams

We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using $O(n^{3\mathrm{/}2}\log (n\mathrm{/}\epsilon )\log n)$ bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for $q=3$. Combining this algorithm with the vertex-sampling lemma of Assadi et al.\ yields, for any $144\lceil {\log }_{2}n\rceil \le Q\le n$, a one-pass decision algorithm distinguishing $3$-colorable graphs from graphs that are not $Q$-colorable using $O((n\mathrm{/}Q{)}^{3\mathrm{/}2}{\log }^{5}n)$ bits of space. This improves upon the $\tilde{O}((n\mathrm{/}Q{)}^2)$ bound achievable via dynamic streaming techniques. Setting $Q=\lceil n^{1\mathrm{/}3}\rceil$ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing $\chi (G)\le q$ from $\chi (G)\ge (q-1{)}^2$ requires $\mathrm{\Omega }(n^2\mathrm{/}{q}^5)$ bits of space, improving upon the previously established $q^2\mathrm{/}4$ threshold using the same space complexity.