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

Our approach is based on the observation that partial coloring can be viewed as a proper coloring problem on a suitable spanning subgraph. By definition, any $k$-partial coloring of a graph $G$ implicitly induces a proper coloring on a subgraph $G^{\prime }\subseteq G$, which acts as a witness for partial coloring: if a coloring is proper on $G^{\prime }$, then every vertex has at least $\min \{k,{\mathrm{deg}}_G(v)\}$ neighbors colored differently in $G$.

We exploit this perspective by explicitly constructing such a witness subgraph. Starting from the input graph $G$, we repeatedly delete edges whose both endpoints currently have degree strictly larger than $k$. This process terminates with a subgraph $G^{\prime }$ in which every edge has at least one endpoint of degree at most $k$. A key property of this construction is that any proper coloring of $G^{\prime }$ is automatically a valid $k$-partial coloring of the original graph $G$.

Once the problem is reduced to properly coloring the witness graph $G^{\prime }$, we aim to apply palette sparsification, following the general strategy of [2]. However, unlike the standard $(\mathrm{\Delta }+1)$-coloring setting, palette sparsification does not immediately apply here: vertices sample colors from the fixed palette $[k+1]$, rather than from degree-dependent palettes. Moreover, we might end up in situations where the graph $G^{\prime }$ has to be properly colored but (refer to Fig. 1). This mismatch prevents a direct application of existing sparsification results.

To overcome this difficulty, we adapt palette sparsification to the structure of the witness graph. The key idea is to exploit the degree asymmetry enforced by the witness construction. We partition the vertices of $G^{\prime }$ into high-degree and low-degree vertices. By construction, the set of high-degree vertices (those with degree greater than $k$) forms an independent set. This allows us to color all high-degree vertices first using a small subset of colors. In particular, we show that they can be colored with at most $k/4$ colors with high probability, using only their randomly sampled palettes.

After fixing the colors of the high-degree vertices, we proceed to color the low-degree vertices. Each low-degree vertex has at most $k$ neighbors in total, and only a small number of colors are forbidden by already-colored neighbors. Although the palettes of these vertices were sampled from $[k+1]$, we show that the effective palettes obtained after removing forbidden colors remain sufficiently large and retain the necessary randomness. This enables the application of a variant of palette sparsification theorem for $(\mathrm{deg}+1)$-list coloring [11, Theorem 4] to complete the coloring.

To translate this existential argument into a streaming algorithm, we introduce a three-phase procedure. In Phase 1 (Filtering), edges are discarded once both endpoints have accumulated degree $k$, ensuring that the maintained graph remains a witness. In Phase 2 (Palette Sparsification), edges whose endpoints have disjoint sampled palettes are discarded, since they cannot induce color conflicts; only potentially constraining edges are stored. Finally, in Phase 3 (Offline Solving), the algorithm solves the resulting demand-partial list coloring instance offline. By the adapted palette sparsification argument, a solution exists with high probability, and any such solution corresponds to a proper coloring of $G^{\prime }$ and hence to a valid $k$-partial coloring of $G$.

We base ourselves on the lower bound technique of [6] who prove that there exists a $\kappa$ such that coloring an input $n$-vertex $\kappa$-degenerate graph $G$ with $\kappa +1$ colors requires $\mathrm{\Omega }(n^2)$ bits in insertion-only stream. Their proof follows a standard reduction from the communication problem Index where Alice is given a vector $X\in {\{0,1\}}^N$ and Bob, an index $i\in [N]$ and Bob outputs the value $X_i$. They follow a standard reduction procedure of shaping $X$ as a square matrix $A[n\times n]$ and the index is mapped as $(g,h)$. These are then encoded as a graph $G^{\prime }$ where two sets of vertices $U$ and $W$ represent the rows and columns of $A$ such that for vertices $u_i\in U$ and $w_j\in W$, $\{u_i,w_j\}\in E(G^{\prime })$ if and only if $A[i,j]=1$. The graph $G^{\prime }$ is encoded in such a way that for any $\kappa +1$ coloring $\gamma$, for vertices $u_g\in U$ and $w_h\in W$, $\gamma (u_g)\ne \gamma (w_h)$ if and only if $A[g,h]=1$.

We follow the same strategy and reshape the vector $X$ into a rectengular matrix $A[(k-1)\times \mathrm{\ell }]$ and the index $i$ mapped as $(t,q)$ and Alice and Bob construct a graph $G$ encoding $A$ and $(t,q)$. Let $R$ and $C$ be the row and column vertices in $G$ corresponding to $A$. Alice ensures that for each vertex $v\in C$ : 1) ${\mathrm{deg}}_G(v)=k-1$ and 2) $\chi (N_G[v])=[k]$ and for each vertex $u\in R$, $|\chi (N_G[u])|=k-1$. Bob, based on the index $(t,q)$ adds edges to the graph ensuring that $\chi (N_G[r_t])=[k-1]$. This is ensured via the special gadgets edge-gadgets and color repeaters which, when added between two vertices force the two vertices to take different and same colors respectively. These properties, along with the fact that any $k$-partial $k$-coloring $\chi$ will color all the incident edges of $v$ properly w.r.t it ensures that $G$ has to satisfy the property that for vertices $r_t\in R$ and $c_q\in C$, $\chi (r_t)\ne \chi (c_q)$ if and only if $A[t,q]=1$.

Any streaming algorithm acts as a one-way communication protocol and in the end, the coloring of the vertices reveal the bit $A[t,q]$. The space bound follows from the fact that the $|V(G)|=O(k+\mathrm{\ell })$, setting $k^{3+\epsilon }=O(\mathrm{\ell })$ and that Index requires $\mathrm{\Omega }(k\mathrm{\ell })$ bit one-way communication bandwidth.

We first establish a lower bound on the degrees in $G^{\prime }$. We claim that for every vertex $v\in V(G)$, ${\mathrm{deg}}_{G^{\prime }}(v)\ge \min \{k,{\mathrm{deg}}_G(v)\}$.

Consider the edge deletion procedure defining $G^{\prime }$. An edge incident to $v$ is removed only if ${\mathrm{deg}}_{current}(v)>k$. Consequently, the degree of $v$ can never be reduced to a value less than $k$, as the removal condition would fail before such a reduction could occur.

• $\mathrm{■}$

  If ${\mathrm{deg}}_G(v)\le k$, the condition $\mathrm{deg}(v)>k$ is never met, so no edges incident to $v$ are ever removed. Thus, ${\mathrm{deg}}_{G^{\prime }}(v)={\mathrm{deg}}_G(v)$.

• $\mathrm{■}$

  If ${\mathrm{deg}}_G(v)>k$, edges incident to $v$ may be removed, but the process must halt for $v$ if its degree reaches $k$. Thus, ${\mathrm{deg}}_{G^{\prime }}(v)\ge k$.

Combining these cases, we have ${\mathrm{deg}}_{G^{\prime }}(v)\ge \min \{k,{\mathrm{deg}}_G(v)\}$.

Now, since $\chi$ is a proper coloring of $G^{\prime }$, $v$ is assigned a color distinct from all its neighbors in $G^{\prime }$. The number of such neighbors is ${\mathrm{deg}}_{G^{\prime }}(v)$. Using our lower bound, the number of neighbors of $v$ in $G$ colored differently than $v$ is at least $\min \{k,{\mathrm{deg}}_G(v)\}$. This satisfies the definition of a $k$-partial coloring. $◀$

Our aim now is to prove palette sparsification for the witness graph $G^{\prime }$. Before proceeding to prove the theorem, we rephrase the palette sparsification theorem for $(\mathrm{deg}+1)$-list coloring [11, Theorem 4] which we will use as a blackbox in our proof.

Without loss of generality, for Theorem 7, we assume that for each vertex $v\in V$, $|L^{\prime }(v)|=\alpha {\log }^{2}n$ for some fixed constant $\alpha$ and each color in $L^{\prime }(v)$ is independently sampled uniformly at random with replacement from the palette of $L(v)$.

We prove the existence of such a coloring using a two-phase randomized procedure. First, for every vertex $v\in V(G^{\prime })$, we split the sampled list $L(v)$ into two disjoint sub-lists $L_1(v)$ and $L_2(v)$ such that $|L_1(v)|=C_1\log n$ and $|L_2(v)|=C_2{\log }^{2}n$ for sufficiently large constants $C_1,C_2$.

We partition the vertex set $V(G^{\prime })$ into two sets: $S=\{v\in V(G^{\prime })\mid {\mathrm{deg}}_{G^{\prime }}(v)>k\}$ and $R=V(G^{\prime })\setminus S$. By the definition of a witness (specifically the constraint that for every edge $\{u,v\}$, $\min \{{\mathrm{deg}}_{G^{\prime }}(u),{\mathrm{deg}}_{G^{\prime }}(v)\}\le k$), no two vertices with degree strictly greater than $k$ can be adjacent. Consequently, $S$ is an independent set in $G^{\prime }$.

The coloring proceeds in two phases:

• $\mathrm{■}$

  Phase 1 (Coloring $S$): We assign colors to vertices in $S$ using only the palettes $L_1(v)$.

• $\mathrm{■}$

  Phase 2 (Coloring $R$): We extend the coloring to $R$ using the palettes $L_2(v)$.

We claim that with high probability, $S$ can be properly colored using a subset of colors $T\subseteq [k+1]$ of size at most $k/4$, such that for every $v\in S$, the assigned color belongs to $L_1(v)\cap T$.

To show this, we construct a bipartite palette graph $P=(S\cup [k+1],E_P)$, where an edge $\{v,c\}$ exists if and only if $c\in L_1(v)$. A subset of colors $T\subseteq [k+1]$ is said to dominate $S$ in $P$ if every vertex $v\in S$ has at least one neighbor in $T$. If such a set $T$ exists, we can define a valid coloring ${\chi }_1$ for $S$ by setting ${\chi }_1(v)=\min \{c\in T\cap L_1(v)\}$. Since $S$ is an independent set, no conflicts can arise between vertices in $S$ regardless of the color choices.

We now show that there exists $T\subseteq [k+1]$ of size $k/4$ that dominates $S$ with high probability. Let $T$ be an arbitrarily chosen but fixed subset of $[k+1]$ with $|T|=k/4$. For any fixed vertex $v\in S$, the probability that $L_1(v)\cap T=\mathrm{\varnothing }$ is

By choosing $C_1$ sufficiently large (e.g., $C_1\ge 12$), we ensure this probability is at most $n^{-3}$. Taking a union bound over all vertices in $S$ (where $|S|\le n$), the probability that there exists any vertex in $S$ not dominated by $T$ is at most $n\cdot n^{-3}=n^{-2}$. Thus, with high probability, there exists a dominating set $T$ of size $k/4$, and consequently a valid coloring ${\chi }_1$ for $S$ using only colors from $T$.

Let ${\chi }_1$ be the coloring of $S$ obtained in Phase 1. Recall that Phase 1 ensures the set of colors used in $S$, denoted $C(S)$, satisfies $|C(S)|\le k/4$.

We extend this coloring to $R$. For each vertex $u\in R$, let $C_{\text{forb}}(u)=\{{\chi }_1(v)\mid v\in N_{G^{\prime }}(u)\cap S\}$ be the set of colors forbidden by neighbors in $S$. We define the target palette for $u$ as $U_u=[k+1]\setminus C_{\text{forb}}(u)$.

Since $u\in R$, we know ${\mathrm{deg}}_{G^{\prime }}(u)\le k$. The number of forbidden colors from $S$ is at most the number of neighbors $u$ has in $S$, which is ${\mathrm{deg}}_{G^{\prime }}(u)-{\mathrm{deg}}_R(u)$. Therefore, it follows easily that $|U_u|\ge {\mathrm{deg}}_R(u)+1$ meaning that a valid extension exists if we had access to $U_u$ and coloring $R$ reduces to solving $(\mathrm{deg}+1)$-list coloring.

At this point, we cannot directly apply Theorem 7 to $R$ as it requires that for vertex $u$, the random list of size at least $\alpha {\log }^{2}n$ be sampled uniformly from the available palette $U_u$ for some constant $\alpha$ while $L_2(u)$ is sampled from $[k+1]$. Let $L_{\text{eff}}(u)=L_2(u)\cap U_u$. We claim that $L_{\text{eff}}(u)$ satisfies the that

1. 1.

   Each color in $L_{\text{eff}}(u)$ is uniformly distributed over $U_u$.

2. 2.

   $|L_{\text{eff}}(u)|\ge \alpha {\log }^{2}n$ with high probability .

The first item follows immediately from Lemma 3.

Now, we show the second item. Since $C_{\text{forb}}(u)\subseteq C(S)$ and $|C(S)|\le k/4$, we have $|U_u|\ge \frac{3}{4}(k+1)$. The size $|L_{\text{eff}}(u)|$ follows a Binomial distribution $B(|L_2(u)|,p)$ with $p=\frac{|U_u|}{k+1}\ge 3/4$. Fix $C_2=8\alpha /3$. Using a Chernoff bound, with $|L_2(u)|=(8/3)\alpha {\log }^{2}n$ and $𝔼[|L_{\text{eff}}(u)|]\ge 2\alpha {\log }^{2}n$, the effective list size $|L_{\text{eff}}(u)|$ is at least $\alpha {\log }^{2}n$ with high probability. Applying union bound, this holds to every vertex in $R$ with high probability.

Since for every vertex $w\in R$, $|L_{\text{eff}}(w)|$ is sufficiently large and conditionally uniform over available palette $U_w$, we can invoke the Palette Sparsification Theorem on the induced subgraph $G^{\prime }[R]$ with palettes $U_w$. This guarantees that a valid coloring ${\chi }_2$ consistent with the lists exists with high probability.

We now combine the results of both phases to bound the total failure probability. Let $E_1$ denote the event that Phase 1 successfully colors $S$ with a subset of colors $T$ such that $|T|\le k/4$. We established that $\mathbb{P}[E_1]\ge 1-n^{-2}$.

Conditioned on the occurrence of $E_1$, the coloring ${\chi }_1$ and the forbidden sets $C_{\text{forb}}(u)$ are well-defined. Let $E_{2\mid 1}$ denote the event that Phase 2 successfully extends this specific coloring to $R$ using the lists $L_2$. Our analysis in Phase 2 demonstrates that for any fixed successful outcome of Phase 1,

The event that a valid $(k+1)$-coloring exists for the entire graph $G^{\prime }$ corresponds to the joint occurrence of both phases succeeding. By the chain rule of probability:

Thus, with high probability, there exists a proper $(k+1)$-coloring ${𝒞}^{\prime }$ of $G^{\prime }$ such that ${𝒞}^{\prime }(v)\in L(v)$ for all $v\in V(G^{\prime })$. $◀$

The vertex set $V$ consists of four disjoint sets of vertices $U=\{u_1,\mathrm{\dots },u_{k-1}\}$, $V=\{v_1,\mathrm{\dots },v_{k-1}\},$ $W=\{w_1,\mathrm{\dots },w_{\mathrm{\ell }}\}$ and $X$ which is a set of auxiliary vertices of cardinality $O(k^3)$ which would be used to create edge-gadgets or repeater gadgets.

1. 1.

   For each distinct pair of vertices $u_i$ and $u_{i^{\prime }}$ with $i\ne i^{\prime }$, insert the edge-gadget $e_{u_i,u_{i^{\prime }}}$.

2. 2.

   For each distinct pair of vertices $v_i$ and $v_{i^{\prime }}$ with $i\ne i^{\prime }$, insert the edge-gadget $e_{v_i,v_{i^{\prime }}}$.

3. 3.

   For every $i\in [k-1]$ and $h\in [\mathrm{\ell }]$: If $A[i,h]=1$, insert the edge $\{u_i,w_h\}$, else insert the edge $\{v_i,w_h\}$.

For every $t\in [k-1]\setminus \{g\}$, insert the color-repeater $c_{u_t,v_t}$ and insert the edge-gadget $e_{u_g,v_g}$.

Alice uses $O(\left(\genfrac{}{}{0pt}{}{k}{2}\right))$ many edge-gadgets (for connecting each pair of vertices in $U$ and $V$ respectively) and Bob uses $(k-2)$ many color-repeaters and $1$ edge-gadget for his stream. They require $O(k^3)$ vertices to build these gadgets and utilize the vertices of $X$ to do so (which has sufficiently many vertices).