No, it is not possible to characterize them. Of course it is possible to find some conditions for special cases but do not hope to find any simple/local dependent rule as this problem is P-complete. Below I give a sketch of how to reduce CVP (Circuit Value Problem) to it.

Before I start one simple observation that you did not mention. For every graph with ordered vertices, there is exactly one coloring that deletes the whole graph. This suggests that in the reduction true variables should correspond to certain edges in our graph rather than to colors.

There will be one main gadget that we use, which I tried to depict here with my humbling artistic laziness.

alt text http://dcg.epfl.ch/webdav/site/dcg/users/184485/public/gadget.JPG

Now I'll try to sketch the reduction. To every node of the circuit we will have a corresponding pair of vertices, $v_1$ and $v_2$, which are next to each other in the order. They will be both black and unconnected before we start deleting them if the node is evaluated as TRUE while $v_1$ will be black, $v_2$ white and they will be connected before we start deleting them if the node is evaluated as FALSE. Thus the above gadget is a negation gate.

Note that the color of 3 changes iff our first variable is true. Thus basically we can modify a later part of the graph arbitrarily by using several copies of this gadget. If we combine two gadgets, we can also simulate an AND gate. For this it is enough to show how to have an edge iff two variables are true. Let A, B, C have this order, at the beginning A being black, A being the "4" in two gadgets, the role of "3" played by B and C in the two gadgets. Then after deleting both variables and A, the color of B and C will be unchanged and there will be an edge between iff both variables were true.

I know that this is a lengthy answer and uses complexity instead of some nice combinatorial observations, but I think it helps to show why there can be no simple characterization. Let me know if you have any questions/would like a more detailed exposition.

Parity. If a graph satisfies that every black vertex has an odd degree and every white vertex has an even degree, then it is not possible to delete it. The proof is by induction on the number of vertices. If there is only one vertex, it must be white, thus we are struck. Otherwise, whenever you delete a black vertex, the parity of the degree of all of its neighbors will change as well as their color, thus we are done by applying the induction hypothesis to this graph.

Warning. I just realized that my reduction is not good as if a node has two outputs, their will be new edges created between them, so we would need a more complicated gadget. I suspect this to be doable, but as meanwhile the question turned out to have a different motivation (see Parity below), I did not give it much thought.

No, it is not possible to characterize them. Of course it is possible to find some conditions for special cases but do not hope to find any simple/local dependent rule as this problem is P-complete. Below I give a sketch of how to reduce CVP (Circuit Value Problem) to it.

Before I start one simple observation that you did not mention. For every graph with ordered vertices, there is exactly one coloring that deletes the whole graph. This suggests that in the reduction true variables should correspond to certain edges in our graph rather than to colors.

There will be one main gadget that we use, which I tried to depict here with my humbling artistic laziness.

alt text http://dcg.epfl.ch/webdav/site/dcg/users/184485/public/gadget.JPG

Now I'll try to sketch the reduction. To every node of the circuit we will have a corresponding pair of vertices, $v_1$ and $v_2$, which are next to each other in the order. They will be both black and unconnected before we start deleting them if the node is evaluated as TRUE while $v_1$ will be black, $v_2$ white and they will be connected before we start deleting them if the node is evaluated as FALSE. Thus the above gadget is a negation gate.

Note that the color of 3 changes iff our first variable is true. Thus basically we can modify a later part of the graph arbitrarily by using several copies of this gadget. If we combine two gadgets, we can also simulate an AND gate. For this it is enough to show how to have an edge iff two variables are true. Let A, B, C have this order, at the beginning A being black, A being the "4" in two gadgets, the role of "3" played by B and C in the two gadgets. Then after deleting both variables and A, the color of B and C will be unchanged and there will be an edge between iff both variables were true.

I know that this is a lengthy answer and uses complexity instead of some nice combinatorial observations, but I think it helps to show why there can be no simple characterization. Let me know if you have any questions/would like a more detailed exposition.

Parity. If a graph satisfies that every black vertex has an odd degree and every white vertex has an even degree, then it is not possible to delete it. The proof is by induction on the number of vertices. If there is only one vertex, it must be white, thus we are struck. Otherwise, whenever you delete a black vertex, the parity of the degree of all of its neighbors will change as well as their color, thus we are done by applying the induction hypothesis to this graph.

No, it is not possible to characterize them. Of course it is possible to find some conditions for special cases but do not hope to find any simple/local dependent rule as this problem is P-complete. Below I give a sketch of how to reduce CVP (Circuit Value Problem) to it.

Before I start one simple observation that you did not mention. For every graph with ordered vertices, there is exactly one coloring that deletes the whole graph. This suggests that in the reduction true variables should correspond to certain edges in our graph rather than to colors.

There will be one main gadget that we use, which I tried to depict here with my humbling artistic laziness.

alt text http://dcg.epfl.ch/webdav/site/dcg/users/184485/public/gadget.JPG

Now I'll try to sketch the reduction. To every node of the circuit we will have a corresponding pair of vertices, $v_1$ and $v_2$, which are next to each other in the order. They will be both black and unconnected before we start deleting them if the node is evaluated as TRUE while $v_1$ will be black, $v_2$ white and they will be connected before we start deleting them if the node is evaluated as FALSE. Thus the above gadget is a negation gate.

Note that the color of 3 changes iff our first variable is true. Thus basically we can modify a later part of the graph arbitrarily by using several copies of this gadget. If we combine two gadgets, we can also simulate an AND gate. For this it is enough to show how to have an edge iff two variables are true. Let A, B, C have this order, at the beginning A being black, A being the "4" in two gadgets, the role of "3" played by B and C in the two gadgets. Then after deleting both variables and A, the color of B and C will be unchanged and there will be an edge between iff both variables were true.

I know that this is a lengthy answer and uses complexity instead of some nice combinatorial observations, but I think it helps to show why there can be no simple characterization. Let me know if you have any questions/would like a more detailed exposition.

No, it is not possible to characterize them. Of course it is possible to find some conditions for special cases but do not hope to find any simple/local dependent rule as this problem is P-complete. Below I give a sketch of how to reduce CVP (Circuit Value Problem) to it.

Before I start one simple observation that you did not mention. For every graph with ordered vertices, there is exactly one coloring that deletes the whole graph. This suggests that in the reduction true variables should correspond to certain edges in our graph rather than to colors.

There will be one main gadget that we use, which I tried to depict here with my humbling artistic laziness.

alt text http://dcg.epfl.ch/webdav/site/dcg/users/184485/public/gadget.JPG

Now I'll try to sketch the reduction. To every node of the circuit we will have a corresponding pair of vertices, $v_1$ and $v_2$, which are next to each other in the order. They will be both black and unconnected before we start deleting them if the node is evaluated as TRUE while $v_1$ will be black, $v_2$ white and they will be connected before we start deleting them if the node is evaluated as FALSE. Thus the above gadget is a negation gate.

Note that the color of 3 changes iff our first variable is true. Thus basically we can modify a later part of the graph arbitrarily by using several copies of this gadget. If we combine two gadgets, we can also simulate an AND gate. For this it is enough to show how to have an edge iff two variables are true. Let A, B, C have this order, at the beginning A being black, A being the "4" in two gadgets, the role of "3" played by B and C in the two gadgets. Then after deleting both variables and A, the color of B and C will be unchanged and there will be an edge between iff both variables were true.

I know that this is a lengthy answer and uses complexity instead of some nice combinatorial observations, but I think it helps to show why there can be no simple characterization. Let me know if you have any questions/would like a more detailed exposition.

Parity. If a graph satisfies that every black vertex has an odd degree and every white vertex has an even degree, then it is not possible to delete it. The proof is by induction on the number of vertices. If there is only one vertex, it must be white, thus we are struck. Otherwise, whenever you delete a black vertex, the parity of the degree of all of its neighbors will change as well as their color, thus we are done by applying the induction hypothesis to this graph.