2
$\begingroup$

Consider the Total Graph ($T(G)$) of a graph $G$ with vertex set $V$ edge set $E=\{(u,v)\}$ with Line graph $L(G)$ and subdivision graph $S(G)$ (formed by putting a vertex in each edge of the original graph). Consider the graph polynomial $P_G=\prod_{(u,v)\in E}(u-v)$ of the graph $G$.

Then, it is easy to see that $P_{T(G)}=P_{G}\cdot P_{L(G)}\cdot P_{S(G)}$.

Can we use the this polynomial to verify the Total coloring conjecture by establishing that the polynomial $P_T(G)$ does not lie in the ideal generated by the polynomials $u^{\Delta+2}-1\ \ ,u\in V\ \ $? Specifically, since the polynomials $P_G$ and $P_{L(G)}$ already do not lie individually in the ideals generated by $u^ {\Delta+2}-1$, thanks to Brooks and Vizings' theorems; and the graph $P(S(G))$, being the polynomial of a bipartite graph, elementarily satisfies the condition. This, coupled with the fact the polynomial ring is an integral domain and the ideal generated by the polynomials $u^{\Delta+2}-1\ \ ,u\in V\ \ $ is a prime ideal (I think) should give us the desired result, right? Are there any overlooked facts here? Thanks beforehand.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The ideal you've defined is not prime since $x^n-1$ is reducible whenever $n>1$. $\endgroup$
    – Gabe Conant
    Commented Jul 13, 2019 at 10:40
  • $\begingroup$ @GabeConant yes, i thought about that, for if it were prime, then just $\Delta+1$ colors would have sufficed, which is clearly false. So we have to reduce $P$ using a suitable grobner basis $\endgroup$
    – vidyarthi
    Commented Jul 13, 2019 at 11:06

0

Reset to default

You must log in to answer this question.