I don't know about the literature on your specific problem but I know this arises as a trivial subquestion of a more general one for which there is literature, most of it from the 19th century.

Let $P_G(x)$ denote your polynomial. If the graph is $k$-regular then you can make a homogenized version
$$
HP_G(x,y)= \prod_{uv\in E}(x_uy_v-x_vy_u)
$$
and then a symmetrized version of the latter $SHP_G$ where you sum over permutations of the pairs $(x_u,y_u)$. What you get is an $SL_2$ invariant of binary forms. In fact you can do this identification in two ways:

1) by seeing the pairs as homogeneous roots and so the invariant is of degree $k$ in the coefficients of a binary form of degree $|V|$,

2) by seeing the pairs as symbolic letters and so the invariant is of degree $|V|$ in the coefficients of a binary form of degree $k$.

The precise relationship between the two interpretations is the isomorphism of $SL_2(\mathbb{C})$ modules
$$
{\rm Sym}^{k}({\rm Sym}^{|V|}(\mathbb{C}^2))\simeq
{\rm Sym}^{|V|}({\rm Sym}^{|k|}(\mathbb{C}^2))
$$
known as Hermite reciprocity.
This also works for nonregular graphs by completing the polynomial with extra factors
$(x_u\times 0 - x_v\times 1)$ involving the "difference with respect to the point at infinity", in which case you get a covariant instead of an invariant. The above Hermite reciprocity covers this more general case too.

Now you see there is a composition of maps:
$$
{\rm graph}\ G\ \rightarrow\ SHP_G\ \rightarrow {\rm invariant\ or\ covariant}
$$
The second is injective and also surjective if one takes linear spans.
The first map however is completely mysterious and highly noninjective. This poses the fundamental question (*that every classical invariant theorist has confronted at some point*):

**How to tell if $SHP_G=0$ simply by looking at the graph?**

The simplest reason for which $SHP_G=0$ is when there exists a permutation as in this MO question. However, this is not the only possibility, as shown by the (multi)graph with
$$
P_G=(x_1-x_2)^2(x_1-x_3)(x_2-x_3)\ .
$$

For pointers to the literature on the wider question I formulated above, see my answer to the MO question Symmetric polynomial from graphs
and in particular the reference to the papers by Sabidussi.