Given a graph $G=(V,E)$ on $n$ vertices, one can associate to it the polynomial $f \in k[x_1,\dots,x_n]$ given by $f = \prod_{\{i,j\}\in E}(x_i - x_j)$. Then one can map various graph properties into ideals ($P\mapsto I_{P}\unlhd k[x_1,\dots,x_n]$) in such a way that $G$ has $P$ iff $f \in I_P$. See e.g. Noga Alon "Combinatorial Nullstellensatz" for details and examples.
Has this approach been useful in solving any graph theoretic problems that are not solvable using purely combinatorial methods? Googling "graph polynomial ideals" returns only a few papers which do not seem to accomplish this.
