It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper coloring of the graph. Specifically, reducing the polynomial with respect to a suitable ideal which is equivalent to a proper $k$ coloring of a graph and checking for nonzero remainder; like for example, the ideal $\langle x_1^k-1,x_2^k-1,\ldots, x_n^k-1\rangle$; or the ideal consisting of all possible graph polynomials of $k$ complete graphs on $n$ vertices; would give us a consensus on whether the graph is $k$-colorable.
But, I wish to ask as to how powerful this technique is. It is seen that the division of multivarite polynomial is quite time consuming , with time complexity in exponential scale; and in addition, the space complexity is also seen to be large. The usual algorithms for graph coloring (like the simple greedy) seem to perform better in the time scale as well as space scale. Are there cases where the polynomial approach outperforms the usual combinatorial approach. Like, for example, is there a clever way of proving the Vizing's or, at least Brooks' theorem using the polynomial approach.
