Yo estaba hablando con mi hermano hoy, y nos encontramos con un poco de conjetura. Es cierto que una gráfica de $G$ orden $n$ está conectado si y sólo si el coeficiente de $x$ en el polinomio cromático $P(G,x)$ es distinto de cero? Esto fue inspirado por resultados como el coeficiente de $x^n$ siempre $1$, el término constante es siempre $0$, el coeficiente de $x^{n-1}=-|E|$, etc.
Hemos sido capaces de demostrar una dirección. Supongamos $G$ está desconectado. A continuación, $G$ es la unión de desconectado componentes, decir $H$ $K$ por razones de simplicidad, y por lo $P(G,x)=P(H,x)P(K,x)$. Pero dado que el término constante de un polinomio cromático siempre es $0$, entonces el menor plazo de $P(H,x)P(K,x)$ al menos $x^2$ desde el mínimo de monomio término de cada es $x$, y así el coeficiente de $x$$0$.
Sin embargo, no pudimos completar la otra dirección. Nuestra idea era coger $G$ a ser un grafo conexo. A continuación, $G$ tiene un árbol de expansión, con cromática polinomio $x(x-1)^{n-1}$, lo que ha $(-1)^{n-1}$ como su coeficiente de $x$. Pensé que podría recuperarse el gráfico original mediante la adición de los bordes de la espalda, y con el hecho de que $P(G,x)=P(G\setminus e,x)-P(G/e,x)$ a de alguna manera introducir, pero no hemos podido completar el argumento. Así es la dirección inversa, verdad? Si es así, ¿cómo demostrarlo? Y si no, hay un contraejemplo? Gracias.
