I am not sure whether you realise this, but the problem you pose is closely related to a problem which has been studied quite widely in connection with measurement based quantum computation (MBQC). I apologize in advance if I do a poor job of explaining MBQC. Let me explain the relationship:

In MBQC a quantum state is initially prepared which acts as a resource for quantum computation. Adaptive measurements are made on local subsystems which drive the computation, with the results eventually appearing in the final measurement outcomes.

By far the most studied class of resource states are known as graph states, because each such state is identified with a graph. The graph state $|\psi_G\rangle$ associated with a graph G=(V,E) is stabilized by $X_j \bigotimes_{k\in Nbgh(j)} Z_k$ $\forall j \in V$. By this I mean that $X_j \bigotimes_{k\in Nbgh(j)} Z_k |\psi_G\rangle = |\psi_G\rangle$. I am using X, Y and Z to denote the two dimensional Pauli operators.

The reason for the relationship is that it has been established that Pauli measurements on graph states yield states locally equivalent to other graph states (see section IIIA in quant-ph/0307130). In particular, the graph identifying the graph state resulting from a Y measurement on vertex j of $|\psi_G\rangle$ is related to G by local complementation with respect to j.

Here local the graphs are not colored (though the coloring will come in later), so the definition of local complementation I use here skips step 2 in your definition.

Let me first note here that we can generate a complete basis for the $2^N$ dimensional Hilbert in which an N vertex graph state $|\psi_G\rangle$ is defined can be generated by simply applying various combinations of local Z operations to $|\psi_G\rangle$. Each such state is orthogonal to the others and to $|\psi_G\rangle$.

When measurements are made on a graph state, they potentially have two outcomes, and these are what I will identify with the coloring. In order to make a measurement pattern deterministic, it is necessary to adapt the measurement basis depending on previous measurement outcomes. The way this is done is fairly simple and since we will only be considering Pauli measurements here we only need to consider flipping measurement outcomes. I'll point you to a paper containing a more detailed description of this at the end.

Now, note that a Y measurement on site j anticommutes with $X_j \bigotimes_{k \in Nbgh(j)} Z_k$, which stabilises the graph state. However, we can note that since we are projecting onto the Y basis on site j, $P_Y^\pm X_j \bigotimes_{k \in Nbgh(j)} Z_k |\psi_G\rangle = P_Y^\pm Z_j \bigotimes_{k \in Nbgh(j)} Z_k |\psi_G\rangle$, where $P^\pm_Y$ are the projectors onto the $\pm 1$ eigenstate of Y. So we can use $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ to calculate the correction operator (see quant-ph/0702212 for more details). So if the Y measurement result is +1, then by applying the operator $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ to resultant state yields a state equivalent to the result of a measurement result of -1.

Now for the coloring: Imagine identifying black with sites which give a measurement outcome of -1 and white with sites which will result in a measurement outcome of +1. Thus applying our correction operator $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ should be equivalent to step 2 in your definition of local complementation. Thus a Y measurement followed by a correction in the MBQC model is equivalent to local complementation as described in your question.

Thus, we can adapt your question as an MBQC problem:
Given a graph $G$ with corresponding graph state $|\psi_G\rangle$, generate a set of local measurements $M$ which results in a continuous sequence of local complementations. Which if any partial time orderings on $M$ can be deterministically corrected?

Admittedly your question is slightly different, since it only asks whether one specific measurement result is correctable, but I think this should at least point you in a useful direction.

Generating $M$ should be straight forward, though the local operators relating the result of a Y measurement to a graph state (described in quant-ph/0307130) complicate matters: Assume the graph is k-colourable. For each vertex v of colour i, associate with vertex v a Y measurement if the number of neighbours of colour previously assigned a Y measurement basis is even, and assign an X measurement if the number of neighbours assigned an Y measurement is odd. Flip the colour of v if the number of neighbours previously assigned a Y measurement mod 4 is either 2 or 3. Increment through i.

So now that we can generate such a set of measurements, the question is simply which partial time orderings on $M$ can be deterministically corrected?

As it turns out, this problem has been studied in great detail, with the existence of flow or g-flow shown to be a sufficient (and in some cases necessary condition). I suspect is it is a necessary condition for this particular problem, but I'm not sure. G-flow is defined in quant-ph/0702212, though quant-ph/0611284 may also be of interest to you.

It is of course possible I have made a slip somewhere in my logic, but if not I believe g-flow may be what you are looking for (though may perhaps not be a sufficient).

Since you only care about a specific measurement result being correctable, I believe this simply reduces to considering only flows which commute with the measurement on a site if the site is black, and anticommute with the measurement operator if the site is white.

I hope this is useful, though of course I realise it is a very weird way to look at the problem.

4more comments