Saltar al contenido principal
LibreTexts Español

5.9: El polinomio cromático

  1. Última actualización
  2. Guardar como PDF
  • Page ID
    117097

    • \( \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}}\)

    Pasamos ahora a la cantidad de formas de colorear una gráfica\(G\) con\(k\) colores. Por supuesto, si\(k< \chi(G)\), esto es cero. Buscamos una función\( P_G(k)\) dando el número de formas de colorear\(G\) con\(k\) colores. Algunas gráficas son fáciles de hacer directamente.

    Ejemplo\(\PageIndex{1}\)

    Si\(G\) es\(K_n\)\( P_G(k)=k(k-1)(k-2)\cdots(k-n+1)\), es decir, el número de permutaciones de\(k\) cosas tomadas\(n\) a la vez. El vértice 1 puede ser coloreado cualquiera de los\(k\) colores, el vértice 2 cualquiera de los\(k-1\) colores restantes, y así sucesivamente. Tenga en cuenta que cuando\(k< n\),\( P_G(k)=0\). Por el Ejercicio 1.E.9.5 en la Sección 1.E, también podemos escribir\( P_G(k)=\sum_{i=0}^n s(n,i)k^i\).

    Ejemplo \(\PageIndex{2}\)

    Si\(G\) tiene\(n\) vértices y no hay aristas,\(P_G(k)=k^n\).

    Dado\(P_G\) que no es difícil de calcular\(\chi(G)\); por ejemplo, podríamos simplemente enchufar los números\(1,2,3,\ldots\) para\(k\) hasta que no\(P_G(k)\) sea cero. Esto sugiere que será difícil (es decir, llevar mucho tiempo) de calcular\(P_G\). Podemos proporcionar un procedimiento mecánico fácil para el cálculo, bastante similar al algoritmo que presentamos para la computación\(\chi(G)\).

    Supongamos que\(G\) tiene borde\(e=\{v,w\}\)\(P_{G-e}(k)\), y considera, la cantidad de formas de colorear\(G-e\) con\(k\) colores. Algunos de los colorantes de también\(G-e\) son colorantes de\(G\), pero algunos no lo son, es decir, aquellos en los que\(v\) y\(w\) tienen el mismo color. ¿Cuántos de estos hay? De nuestra discusión del algoritmo para\(\chi(G)\) sabemos que este es el número de colorantes de\(G/e\). Así,\[ P_G(k)=P_{G-e}(k)-P_{G/e}(k). \nonumber\] ya que\(G-e\)\(G/e\) ambos tienen menos aristas que\(G\), podemos calcular\(P_G\) aplicando esta fórmula recursivamente. En definitiva, solo necesitamos computar\(P_G\) para gráficas sin bordes, lo cual es fácil, como en Ejemplo\(\PageIndex{2}\).

    Desde\(P_G(k)=k^n\) cuando no\(G\) tiene aristas, entonces es fácil de ver, y de probar por inducción, que\(P_G\) es un polinomio.

    Teorema \(\PageIndex{1}\)

    Para todos\(G\) en\(n\) vértices,\(P_G\) es un polinomio de grado\(n\), y\(P_G\) se llama el polinomio cromático de\(G\).

    Prueba

    La prueba es por inducción en el número de bordes en\(G\). Cuando no\(G\) tiene bordes, esto es Ejemplo\(\PageIndex{2}\).

    De lo contrario, por la hipótesis de inducción,\(P_{G-e}\) es un polinomio de grado\(n\) y\(P_{G/e}\) es un polinomio de grado\(n-1\), así\( P_G=P_{G-e}-P_{G/e}\) es un polinomio de grado\(n\).

    El polinomio cromático de una gráfica tiene una serie de propiedades interesantes y útiles, algunas de las cuales se exploran en los ejercicios.

    Colaboradores y Atribuciones

    This page titled 5.9: El polinomio cromático is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard.