Return to Question

Consider a suitable vertex ordering for the simple graphs. Now, consider the graph polynomial $\prod_{i<j}(x_i-x_j)$ where $i,j$ range over all vertices of the simple graph. Now, let $rad(\prod_{k=1}^tx_i^{e_i})$ denote the number of distinct $e_i$s in a single monomial of the monomial representation of the polynomial defined above.

Then,if the graph be regular, I think that the chromatic number is the maximum of $rad$ among all monomials in the polynomial as defined, provided the graph is not complete or an odd cycle. This is because, 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 reuced 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 distinct $e_is$ give the chromatic number. For example, if we consider the $4$ cycle with $4$ vertices labeled $1,2,3,4$, we have the graph polynomial $$(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. This 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 the right approach, or are there counterexamples. Thanks beforehand.

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.

Consider a suitable vertex ordering for the simple graphs. Now, consider the graph polynomial $\prod_{i<j}(x_i-x_j)$ where $i,j$ range over all vertices of the simple graph. Now, let $rad(\prod_{k=1}^tx_i^{e_i})$ denote the number of distinct $e_i$s in a single monomial of the monomial representation of the polynomial defined above.

Then,if the graph be regular, I think that the chromatic number is the maximum of $rad$ among all monomials in the polynomial as defined, provided the graph is not complete or an odd cycle. This is because, 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 reuced 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 distinct $e_is$ give the chromatic number. For example, if we consider the $4$ cycle with $4$ vertices labeled $x1,x2,x3,x4$, we have the graph polynomial $$(x1-x2)(x1-x4)(x2-x3)(x3-x4)=x1^2x2*x3 - x1^2*x2*x4 - x1^2*x3^2 + x1^2*x3*x4 - x1*x2^2*x3 + x1*x2^2*x4 + x1*x2*x3^2 + (-2)*x1*x2*x3*x4 + x1*x2*x4^2 + x1*x3^2*x4 - x1*x3*x4^2 + x2^2*x3*x4 - x2^2*x4^2 - x2*x3^2*x4 + x2*x3*x4^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. This 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 the right approach, or are there counterexamples. Thanks beforehand.

Consider a suitable vertex ordering for the simple graphs. Now, consider the graph polynomial $\prod_{i<j}(x_i-x_j)$ where $i,j$ range over all vertices of the simple graph. Now, let $rad(\prod_{k=1}^tx_i^{e_i})$ denote the number of distinct $e_i$s in a single monomial of the monomial representation of the polynomial defined above.

Then,if the graph be regular, I think that the chromatic number is the maximum of $rad$ among all monomials in the polynomial as defined, provided the graph is not complete or an odd cycle. This is because, 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 reuced 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 distinct $e_is$ give the chromatic number. For example, if we consider the $4$ cycle with $4$ vertices labeled $1,2,3,4$, we have the graph polynomial $$(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. This 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 the right approach, or are there counterexamples. Thanks beforehand.

Consider a suitable vertex ordering for the simple graphs. Now, consider the graph polynomial $\prod_{i<j}(x_i-x_j)$ where $i,j$ range over all vertices of the simple graph. Now, let $rad(\prod_{k=1}^tx_i^{e_i})$ denote the number of distinct $e_i$s in the monomial representation of the polynomial defined above.

Then,if the graph be regular, I think that the chromatic number is the maximum of $rad$ among all monomials in the polynomial as defined, provided the graph is not complete or an odd cycle. This is because, 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 reuced 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 distinct $e_is$ give the chromatic number. For example, if we consider the $4$ cycle with $4$ vertices labeled $x1,x2,x3,x4$, we have the graph polynomial $$(x1-x2)(x1-x4)(x2-x3)(x3-x4)=x1^2x2*x3 - x1^2*x2*x4 - x1^2*x3^2 + x1^2*x3*x4 - x1*x2^2*x3 + x1*x2^2*x4 + x1*x2*x3^2 + (-2)*x1*x2*x3*x4 + x1*x2*x4^2 + x1*x3^2*x4 - x1*x3*x4^2 + x2^2*x3*x4 - x2^2*x4^2 - x2*x3^2*x4 + x2*x3*x4^2$$ Here, it is easily seen that $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, which are exceptions. This 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 the right approach, or are there counterexamples. Thanks beforehand.

Consider a suitable vertex ordering for the simple graphs. Now, consider the graph polynomial $\prod_{i<j}(x_i-x_j)$ where $i,j$ range over all vertices of the simple graph. Now, let $rad(\prod_{k=1}^tx_i^{e_i})$ denote the number of distinct $e_i$s in a single monomial of the monomial representation of the polynomial defined above.

Then,if the graph be regular, I think that the chromatic number is the maximum of $rad$ among all monomials in the polynomial as defined, provided the graph is not complete or an odd cycle. This is because, 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 reuced 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 distinct $e_is$ give the chromatic number. For example, if we consider the $4$ cycle with $4$ vertices labeled $x1,x2,x3,x4$, we have the graph polynomial $$(x1-x2)(x1-x4)(x2-x3)(x3-x4)=x1^2x2*x3 - x1^2*x2*x4 - x1^2*x3^2 + x1^2*x3*x4 - x1*x2^2*x3 + x1*x2^2*x4 + x1*x2*x3^2 + (-2)*x1*x2*x3*x4 + x1*x2*x4^2 + x1*x3^2*x4 - x1*x3*x4^2 + x2^2*x3*x4 - x2^2*x4^2 - x2*x3^2*x4 + x2*x3*x4^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. This 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 the right approach, or are there counterexamples. Thanks beforehand.