5.3: Deleción-Contracción y el Polinomio Cromático

Última actualización
Guardar como PDF

Page ID: 112563

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\(\rightarrow\) Exercise 243

En el Capítulo 2 se introdujo la recurrencia deleción-contracción para contar árboles de expansión de una gráfica. Averiguar cómo se relaciona el polinomio cromático de una gráfica con los resultantes de la eliminación de un borde\(e\) y de la contracción de ese mismo borde\(e\). Trate de encontrar una recurrencia como la de contar árboles de expansión que exprese el polinomio cromático de una gráfica en términos de los polinomios cromáticos de\(G − e\) y\(G/e\) para un borde arbitrario\(e\). Utilice esta recurrencia para dar otra prueba de que el número de formas de colorear una gráfica con\(x\) colores es una función polinómica de\(x\). (Pista).

Ejercicio 244

Utilice la recurrencia deleción-contracción para reducir el cálculo del polinomio cromático de la gráfica en la Figura 5.3.1 para el cálculo de polinomios cromáticos que pueda calcular fácilmente. (Puede simplificar sus cálculos pensando en el efecto en el polinomio cromático de eliminar un borde que es un bucle, o eliminar uno de varios bordes entre los mismos dos vértices).

Figura\(\PageIndex{1}\): Una gráfica. (Copyright; autor vía fuente)

\(\rightarrow\) Exercise 245

¿De cuántas maneras puedes colorear correctamente los vértices de un trazado en\(n\) vértices con\(x\) colores? Describir cualquier dependencia del polinomio cromático de una trayectoria sobre el número de vértices.
(No tremendamente duro.) ¿De cuántas maneras puedes colorear correctamente los vértices de un ciclo en\(n\) vértices con\(x\) colores? Describir cualquier dependencia del polinomio cromático de un ciclo sobre el número de vértices.

Ejercicio 246

¿De cuántas maneras puedes colorear correctamente los vértices de un árbol en\(n\) vértices con\(x\) colores? (Pista).

\(\rightarrow\) Exercise 247

¿Qué observa sobre los signos de los coeficientes del polinomio cromático de la gráfica en la Figura 5.3.1? ¿Y los signos de los coeficientes del polinomio cromático de un camino? ¿De un ciclo? ¿De un árbol? Hacer una conjetura sobre los signos de los coeficientes de un polinomio cromático y probarlo.

Colaboradores y Atribuciones

Template:ContribBogart