Chromatic number and graph polynomial

Question

If $\prod_{i=1}^t x_i^{e_i}$ is a monomial, define $$rad\biggl(\prod_{i=1}^t x_i^{e_i}\biggr)$$ to be the number of distinct (nonzero) values of $e_i$. Now let $G$ be a simple graph with vertices labeled by integers, and consider the graph polynomial $$P_G := \prod_{i<j}(x_i-x_j)$$ where the product is over all edges $\{i,j\}$ of the simple graph. I believe that the following is true.

Claim. If $G$ is a regular simple graph, not a complete graph or an odd cycle, then the chromatic number of $G$ is equal to the maximum value of $rad(m)$ as $m$ ranges over all monomials appearing in $P_G$.

My argument is that, when we multiply the polynomial factors of the graph polynomial, if two vertices belong to the same independent set and are not adjacent, then they will give the same exponent in the multiplication, provided the graph be regular. But, if the next sequence in the order of vertices be adjacent to previous vertices, then, they would have one exponent reduced in the leading term polynomial with the defined order, thereby giving a reduced exponent (by $1$). Continuing so on, the leading term of the monomial with respect to some order would be of the form $x_1^{e_1}x_2^{e_1-1}\ldots$ where the number of distinct $e_i$ give the chromatic number. For example, if we let $G$ be the $4$-cycle with $4$ vertices labeled $1,2,3,4$, then $P_G$ is $$(x_1-x_2)(x_1-x_4)(x_2-x_3)(x_3-x_4)=x_1^2x_2x_3 - x_1^2x_2x_4 - x_1^2x_3^2 + x_1^2x_3x_4 - x_1x_2^2x_3 + x_1x_2^2x_4 + x_1x_2x_3^2 - 2x_1x_2x_3x_4 + x_1x_2x_4^2 + x_1x_3^2x_4 - x_1x_3x_4^2 + x_2^2x_3x_4 - x_2^2x_4^2 - x_2x_3^2x_4 + x_2x_3x_4^2.$$ Here, it is easily seen that the maximum $rad$ of polynomial is $2$, whence the graph is $2$ colorable. Though this is an elementary example, but I think it extends to higher size regular graphs as well. As regards complete graphs and odd cycles, these are exceptions.

If true, the Claim would lead to a proof of Brooks theorem, as the maximum number of $rad$ for any graph polynomial would be $\Delta$, where $\Delta$ is the maximum degree, which can be seen by noticing that the decreasing sequence of exponents starts from $\Delta$ and ends, at the maximum at $1$.

Is this argument correct, or are there counterexamples? Thanks beforehand.

Answer 1

$G=K_{3,3}$ is a counterexample: it has chromatic number $2$ but $\mathrm{rad}(P_G)=3$; there are monomials with all three exponents $1,2,3$.

My conjecture would be that $\mathrm{rad}(P_G)$ is equal to the (maximum) degree of $G$ if $G$ is regular.

---

Edit:

I claim that if $G$ is a bipartite $k$-regular graph, then $\mathrm{rad}(P_G)=k$. This can be seen as follows. Let $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_n$ be the two color classes of $G$. We may then write $P_G$ as the product of terms $(x_i-y_j)$ where $x_iy_j$ is an edge of $G$. Every monomial $x_1^{e_1}\dots x_n^{e_n}y_1^{f_1}\dots y_n^{f_n}$ appears in $P_G$ with sign $(-1)^{f_1+\cdots +f_n}$, so they never cancel out (unlike the square-free monomial in the case of odd cycles).

Since $n\ge k$, for $i\le k$ we can select $x_i$ from exactly $i$ terms $(x_i-y_j)$, and otherwise select $y_j$. These will multiply to a monomial $x_1^{1}x_2^2 \dots x_k^k x_{k+1}^{e_{k+1}}\dots x_n^{e_n}y_1^{f_1}\dots y_n^{f_n}$, which has $k$ different exponents $1,2,\dots,k$.

This proves my conjecture for bipartite graphs. For non-bipartite graphs it may be trickier because of possible cancellations of some monomials.