# Chromatic number and graph polynomial

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 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.

• I don't understand your definition of rad. Do you mean that to compute rad of a multivariate polynomial, you expand it completely into monomials, and then for each monomial $m$, you look at the set $\{e_i\}$ of exponents of the variables occurring in $m$, and count how many distinct values occur, and then finally you're taking the maximum over all $m$? – Timothy Chow Jul 29 '19 at 13:56
• @TimothyChow you are right. But I define $rad$ here only for a single monomial. And the maximum value of $rad$ is as yousay, take maximum value over all the single monomial $rad$ – vidyarthi Jul 29 '19 at 14:56
• I have taken the liberty of editing your post to clarify it. Please check to make sure that I have correctly expressed your intent. – Timothy Chow Jul 30 '19 at 14:44
• @TimothyChow it is quite presentable now. But, what are your thoughts regarding the truth of the assertion – vidyarthi Jul 30 '19 at 16:31
• I haven't thought about it much but if an odd cycle is a counterexample then so is a disjoint union of odd cycles, and I would guess that other graphs built out of odd cycles in some way might be counterexamples too. – Timothy Chow Jul 30 '19 at 18:40

$$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.

• thanks!, now my new conjecture, using the similar argument in my question, is that $min(rad)=\chi-1$, where $\chi$ is chromatic number. Any fast counterexamples? – vidyarthi Jul 31 '19 at 15:17
• I would suggest to try $K_{n,n}$, or the graph of the $n$-dimensional hypercube. Both are bipartite with large degrees. But it is not so straightforward to compute their $P_G$. Moreover, the $4$-cycle would be a counterexample to the new conjecture. Actually for bipartite graphs the monomials in $P_G$ never cancel out, so $\mathrm{rad}(P_G)$ can be determined quite easily. I will update the answer. – Jan Kyncl Jul 31 '19 at 22:49
• The $4-$ cycle is not a counterexample to the new conjecture, because, it has the monomial $x_1^2x_3^2$, which has only one distinct nonzero exponent. Yes, as you told, the main problem is with cancelation of terms. If cancelation were not an issue, then I would claim that minimising the number of variables, the $min(rad)$ would be equal to $\chi-1$, because when minimizing the number of variables, we have to maximize the exponents(homogeneous poly), which will clearly partition the vertices to different color classes – vidyarthi Aug 1 '19 at 8:19
• I see, the new conjecture is about $\min(\mathrm{rad})$, not $\max(\mathrm{rad})$. For $K_4$ it is possible to get a monomial $x_1^2x_2^2x_3^2$, but it will cancel out. Perhaps the new conjecture could be asked as a separate question. – Jan Kyncl Aug 2 '19 at 2:13