As a continuation of this question and as stated in the comments, I wish to ask if the minimum value of $rad$ for all monomials equals the chromatic number when the number of variables in a monomial is minimized.

This is because, when the number of variables is minimized; and the polynomial is homogeneous, therefore the degree of each individual variable must be maximised. This is turn, forces the variables having distinct powers to belong to different independent sets (for, otherwise, the variables which belong a single independent set would have the same exponent as they are not adjacent to each other).

The other, proper way of proving would be to consider the remainder when the graph polynomial is divided by the ideal $\langle x_1^k-1,x_2^k-1,\ldots,x_n^k-1\rangle$ where $k$ is the value of $min(rad)+1$ with variables minimized. However, this takes the entire graph polynomial into account, and hence is difficult to analyze per se. Is the assertion wrong? Any counterexamples. Thanks beforehand.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.