The q-zero forcing conjecture for complete multipartite graphs

The conjecture fails for part size $n=1$. More generally, its exact corrected form can be proved for every parameter.

Let $G=K_{n,\ldots,n}$ have $\ell\ge3$ parts and $N=n\ell$ vertices. Then

$$Z_q(G)= \begin{cases} n(\ell-1),&q=0,\\ \ell-1,&q\ge1,\ n=1,\\ n\ell-2,&q\ge1,\ n\ge2. \end{cases}$$

For $q=0$, the standard connectivity lower bound gives

$$Z_0(G)\ge\kappa(G)=N-n.$$

Conversely, color all vertices outside one part. The remaining white vertices are singleton components, and the $q=0$ oracle can be offered one singleton at a time, enabling a colored vertex outside that part to force it. Therefore

$$Z_0(G)=N-n=n(\ell-1).$$

Now suppose $q\ge1$. If the white vertices occupy at least two parts, their induced graph is connected, so there are fewer than $q+1$ white components and the oracle rule cannot be invoked. If all white vertices occupy one part, they are singleton components. Whenever at least $q+1\ge2$ are offered, the oracle can return exactly two. Every colored vertex outside their part is adjacent to both returned vertices, while every colored vertex inside that part is adjacent to neither. Hence no force is possible. This gives an oracle strategy neutralizing every special move, and therefore

$$Z_q(G)=Z(G)\qquad(q\ge1).$$

If $n\ge2$, coloring all but one vertex in each of two different parts produces a zero-forcing set of size $N-2$. Conversely, with at least three white vertices, any possible standard force must remove the sole white vertex outside some part, leaving at least two white vertices in that part; these cannot subsequently be distinguished or forced. Thus

$$Z(G)=N-2\qquad(n\ge2).$$

If $n=1$, however, $G=K_\ell$, and

$$Z_q(K_\ell)=Z(K_\ell)=\ell-1\qquad(q\ge1).$$

In particular,

$$n=1,\qquad\ell=3,\qquad q=1$$

gives

$$Z_1(K_3)=2\ne1=n\ell-2.$$

Hence the original conjecture is false as stated, while its corrected version holds for all $n\ge2$.