Polinomio cromático

Función en la teoría de grafos algebraicos

Todos los grafos no isomorfos sobre 3 vértices y sus polinomios cromáticos, en el sentido de las agujas del reloj desde arriba. El 3-conjunto independiente: k ³ . Una arista y un único vértice: k ² ( k – 1) . El 3-camino: k ( k – 1) ² . La 3-camarilla: k ( k – 1)( k – 2) .

El polinomio cromático es un polinomio de grafos estudiado en la teoría de grafos algebraicos , una rama de las matemáticas . Cuenta el número de coloraciones de grafos en función del número de colores y fue definido originalmente por George David Birkhoff para estudiar el problema de los cuatro colores . Fue generalizado al polinomio de Tutte por Hassler Whitney y WT Tutte , vinculándolo al modelo de Potts de física estadística .

Historia

George David Birkhoff introdujo el polinomio cromático en 1912, definiéndolo sólo para grafos planares , en un intento de demostrar el teorema de los cuatro colores . Si denota el número de coloraciones propias de G con k colores, entonces se podría establecer el teorema de los cuatro colores demostrando para todos los grafos planares G. De esta manera, esperaba aplicar las poderosas herramientas del análisis y el álgebra para estudiar las raíces de los polinomios al problema de coloración combinatoria. ${\displaystyle P(G,k)}$ ${\displaystyle P(G,4)>0}$

En 1932, Hassler Whitney generalizó el polinomio de Birkhoff del caso planar a los grafos generales. En 1968, Ronald C. Read preguntó qué polinomios son los polinomios cromáticos de algún grafo, una pregunta que sigue abierta, e introdujo el concepto de grafos cromáticamente equivalentes. ^[1] Hoy en día, los polinomios cromáticos son uno de los objetos centrales de la teoría de grafos algebraicos . ^[2]

Definición

Todas las coloraciones de vértices adecuadas de los gráficos de vértices con 3 vértices utilizando k colores para . El polinomio cromático de cada gráfico se interpola a través del número de coloraciones adecuadas. ${\displaystyle k=0,1,2,3}$

Para un grafo G , cuenta el número de sus k -coloraciones (propias) de vértice . Otras notaciones de uso común incluyen , , o . Existe un único polinomio que evaluado en cualquier entero k ≥ 0 coincide con ; se denomina polinomio cromático de G . ${\displaystyle P(G,k)}$ ${\displaystyle P_{G}(k)}$ ${\displaystyle \chi _{G}(k)}$ ${\displaystyle \pi _{G}(k)}$ ${\displaystyle P(G,x)}$ ${\displaystyle P(G,k)}$

Por ejemplo, para colorear el grafo de trayectorias en 3 vértices con k colores, se puede elegir cualquiera de los k colores para el primer vértice, cualquiera de los colores restantes para el segundo vértice y, por último, para el tercer vértice, cualquiera de los colores que sean diferentes a la elección del segundo vértice. Por lo tanto, es el número de k -coloraciones de . Para una variable x (no necesariamente entera), tenemos . (Las coloraciones que difieren solo por permutación de colores o por automorfismos de G se cuentan como diferentes). ${\displaystyle P_{3}}$ ${\displaystyle k-1}$ ${\displaystyle k-1}$ ${\displaystyle P(P_{3},k)=k\cdot (k-1)\cdot (k-1)}$ ${\displaystyle P_{3}}$ ${\displaystyle P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x}$

Deleción-contracción

El hecho de que el número de k -coloraciones sea un polinomio en k se desprende de una relación de recurrencia llamada recurrencia de supresión-contracción o Teorema de Reducción Fundamental . ^[3] Se basa en la contracción de aristas : para un par de vértices y el grafo se obtiene fusionando los dos vértices y eliminando cualquier arista entre ellos. Si y son adyacentes en G , sea el grafo obtenido al eliminar la arista . Entonces los números de k -coloraciones de estos grafos satisfacen: ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G/uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G-uv}$ ${\displaystyle uv}$

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k)}$

De manera equivalente, si y no son adyacentes en G y es el gráfico con la arista agregada, entonces ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G+uv}$ ${\displaystyle uv}$

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k)}$

Esto se desprende de la observación de que cada k -coloración de G da colores diferentes a y , o bien los mismos colores. En el primer caso, esto da una k -coloración (adecuada) de , mientras que en el segundo caso da una coloración de . A la inversa, cada k -coloración de G se puede obtener de forma única a partir de una k -coloración de o (si y no son adyacentes en G ). ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G+uv}$ ${\displaystyle G/uv}$ ${\displaystyle G+uv}$ ${\displaystyle G/uv}$ ${\displaystyle u}$ ${\displaystyle v}$

El polinomio cromático puede entonces definirse recursivamente como

${\displaystyle P(G,x)=x^{n}}$para el grafo sin aristas en n vértices, y

${\displaystyle P(G,x)=P(G-uv,x)-P(G/uv,x)}$para un grafo G con una arista (elegida arbitrariamente). ${\displaystyle uv}$

Puesto que el número de k -coloraciones del grafo sin aristas es de hecho , se sigue por inducción sobre el número de aristas que para todo G , el polinomio coincide con el número de k -coloraciones en cada punto entero x  =  k . En particular, el polinomio cromático es el único polinomio de interpolación de grado como máximo n a través de los puntos ${\displaystyle k^{n}}$ ${\displaystyle P(G,x)}$

${\displaystyle \left\{(0,P(G,0)),(1,P(G,1)),\ldots ,(n,P(G,n))\right\}.}$

La curiosidad de Tutte sobre qué otros invariantes gráficos satisfacían tales recurrencias lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte . ${\displaystyle T_{G}(x,y)}$

Ejemplos

Propiedades

Para G fijo en n vértices, el polinomio cromático es un polinomio mónico de grado exactamente n , con coeficientes enteros. ${\displaystyle P(G,x)}$

El polinomio cromático incluye al menos tanta información sobre la colorabilidad de G como el número cromático. De hecho, el número cromático es el entero positivo más pequeño que no es un cero del polinomio cromático.

${\displaystyle \chi (G)=\min\{k\in \mathbb {N} :P(G,k)>0\}.}$

El polinomio evaluado en , es decir , produce veces el número de orientaciones acíclicas de G . ^[4] ${\displaystyle -1}$ ${\displaystyle P(G,-1)}$ ${\displaystyle (-1)^{|V(G)|}}$

La derivada evaluada en 1, es igual al invariante cromático hasta el signo. ${\displaystyle P'(G,1)}$ ${\displaystyle \theta (G)}$

Si G tiene n vértices y c componentes , entonces ${\displaystyle G_{1},\ldots ,G_{c}}$

• Los coeficientes de son ceros. ${\displaystyle x^{0},\ldots ,x^{c-1}}$
• Los coeficientes de son todos distintos de cero y se alternan en signos. ${\displaystyle x^{c},\ldots ,x^{n}}$
• El coeficiente de es 1 (el polinomio es mónico ). ${\displaystyle x^{n}}$
• El coeficiente de es ${\displaystyle x^{n-1}}$ ${\displaystyle -|E(G)|.}$

Demostramos esto por inducción sobre el número de aristas en un grafo simple G con vértices y aristas. Cuando , G es un grafo vacío. Por lo tanto, por definición . Entonces, el coeficiente de es , lo que implica que la afirmación es verdadera para un grafo vacío. Cuando , como en G tiene solo una arista, . Por lo tanto, el coeficiente de es . Entonces, la afirmación es válida para k = 1. Usando inducción fuerte , supongamos que la afirmación es verdadera para . Sea G tiene aristas. Por el principio de contracción-eliminación , ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=0}$ ${\displaystyle P(G,x)=x^{n}}$ ${\displaystyle x^{n-1}}$ ${\displaystyle 0}$ ${\displaystyle k=1}$ ${\displaystyle P(G,x)=x^{n}-x^{n-1}}$ ${\displaystyle x^{n-1}}$ ${\displaystyle -1=-|E(G)|}$ ${\displaystyle k=0,1,2,\ldots ,(k-1)}$ ${\displaystyle k}$

${\displaystyle P(G,x)=P(G-e,x)-P(G/e,x),}$

Sea y Por lo tanto . Puesto que se obtiene de G eliminando solo una arista e , , entonces y por lo tanto la afirmación es verdadera para k . ${\displaystyle P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots ,}$ ${\displaystyle P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots .}$
${\displaystyle P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots }$
${\displaystyle G-e}$ ${\displaystyle a_{n-1}=k-1}$ ${\displaystyle a_{n-1}+1=k}$

• El coeficiente de es multiplicado por el número de orientaciones acíclicas que tienen un sumidero único, en un vértice especificado, elegido arbitrariamente. ^[5] ${\displaystyle x^{1}}$ ${\displaystyle (-1)^{n-1}}$
• Los valores absolutos de los coeficientes de cada polinomio cromático forman una secuencia logarítmica-cóncava . ^[6]
• ${\displaystyle \scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c},x)}$

La última propiedad se generaliza por el hecho de que si G es una suma k -clique de y (es decir, un gráfico obtenido al pegar los dos en una camarilla en k vértices), entonces ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

${\displaystyle P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots (x-k+1)}}.}$

Un grafo G con n vértices es un árbol si y sólo si

${\displaystyle P(G,x)=x(x-1)^{n-1}.}$

Equivalencia cromática

Las tres gráficas con un polinomio cromático igual a . ${\displaystyle (x-2)(x-1)^{3}x}$

Se dice que dos grafos son cromáticamente equivalentes si tienen el mismo polinomio cromático. Los grafos isomorfos tienen el mismo polinomio cromático, pero los grafos no isomorfos pueden ser cromáticamente equivalentes. Por ejemplo, todos los árboles en n vértices tienen el mismo polinomio cromático. En particular, es el polinomio cromático tanto del grafo de garra como del grafo de trayectoria en 4 vértices. ${\displaystyle (x-1)^{3}x}$

Un grafo es cromáticamente único si está determinado por su polinomio cromático, salvo isomorfismo. En otras palabras, G es cromáticamente único, lo que implicaría que G y H son isomorfos. Todos los grafos cíclicos son cromáticamente únicos. ^[7] ${\displaystyle P(G,x)=P(H,x)}$

Raíces cromáticas

Una raíz (o cero ) de un polinomio cromático, llamada “raíz cromática”, es un valor x donde . Las raíces cromáticas han sido muy bien estudiadas, de hecho, la motivación original de Birkhoff para definir el polinomio cromático fue mostrar que para gráficos planares, para x ≥ 4. Esto habría establecido el teorema de los cuatro colores . ${\displaystyle P(G,x)=0}$ ${\displaystyle P(G,x)>0}$

Ningún grafo puede ser de color 0, por lo que 0 es siempre una raíz cromática. Solo los grafos sin aristas pueden ser de color 1, por lo que 1 es una raíz cromática de cada grafo con al menos una arista. Por otro lado, excepto estos dos puntos, ningún grafo puede tener una raíz cromática en un número real menor o igual a 32/27. ^[8] Un resultado de Tutte conecta la proporción áurea con el estudio de las raíces cromáticas, mostrando que las raíces cromáticas existen muy cerca de : Si es una triangulación plana de una esfera entonces ${\displaystyle \varphi }$ ${\displaystyle \varphi ^{2}}$ ${\displaystyle G_{n}}$

${\displaystyle P(G_{n},\varphi ^{2})\leq \varphi ^{5-n}.}$

Si bien la línea real tiene grandes partes que no contienen raíces cromáticas para ningún gráfico, cada punto en el plano complejo está arbitrariamente cerca de una raíz cromática en el sentido de que existe una familia infinita de gráficos cuyas raíces cromáticas son densas en el plano complejo. ^[9]

Dibujos para colorear usando todos los colores

Para un grafo G en n vértices, sea la cantidad de coloraciones que utilizan exactamente k colores hasta cambiar el nombre de los colores (de modo que las coloraciones que se pueden obtener entre sí permutando colores se cuentan como una; las coloraciones obtenidas por automorfismos de G se siguen contando por separado). En otras palabras, cuenta la cantidad de particiones del conjunto de vértices en k conjuntos independientes (no vacíos) . Luego cuenta la cantidad de coloraciones que utilizan exactamente k colores (con colores distinguibles). Para un entero x , todas las x -coloraciones de G se pueden obtener de forma única eligiendo un entero k ≤ x , eligiendo k colores para utilizar de los x disponibles y una coloración que utilice exactamente esos k colores (distinguibles). Por lo tanto: ${\displaystyle e_{k}}$ ${\displaystyle e_{k}}$ ${\displaystyle k!\cdot e_{k}}$

${\displaystyle P(G,x)=\sum _{k=0}^{x}{\binom {x}{k}}k!\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k},}$

donde denota el factorial descendente . Por lo tanto, los números son los coeficientes del polinomio en la base de los factoriales descendentes. ${\displaystyle (x)_{k}=x(x-1)(x-2)\cdots (x-k+1)}$ ${\displaystyle e_{k}}$ ${\displaystyle P(G,x)}$ ${\displaystyle 1,(x)_{1},(x)_{2},(x)_{3},\ldots }$

Sea el k -ésimo coeficiente de en la base estándar , es decir: ${\displaystyle a_{k}}$ ${\displaystyle P(G,x)}$ ${\displaystyle 1,x,x^{2},x^{3},\ldots }$

${\displaystyle P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}}$

Los números de Stirling dan un cambio de base entre la base estándar y la base de los factoriales descendentes. Esto implica:

${\displaystyle a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}}$   y   ${\displaystyle e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}.}$

Categorización

El polinomio cromático se clasifica mediante una teoría de homología estrechamente relacionada con la homología de Khovanov . ^[10]

Algoritmos

Los problemas computacionales asociados con el polinomio cromático incluyen

• encontrar el polinomio cromático de un grafo dado G ; ${\displaystyle P(G,x)}$
• evaluando en un x fijo para un G dado . ${\displaystyle P(G,x)}$

El primer problema es más general porque si supiéramos los coeficientes de podríamos evaluarlo en cualquier punto del tiempo polinomial porque el grado es n . La dificultad del segundo tipo de problema depende en gran medida del valor de x y se ha estudiado intensamente en complejidad computacional . Cuando x es un número natural, este problema normalmente se considera como el cálculo del número de x -coloraciones de un gráfico dado. Por ejemplo, esto incluye el problema #3-coloración de contar el número de 3-coloraciones, un problema canónico en el estudio de la complejidad del conteo, completo para la clase de conteo #P . ${\displaystyle P(G,x)}$

Algoritmos eficientes

Para algunas clases de gráficos básicos, se conocen fórmulas cerradas para el polinomio cromático. Por ejemplo, esto es cierto para árboles y grupos, como se indica en la tabla anterior.

Los algoritmos de tiempo polinomial son conocidos por calcular el polinomio cromático para clases más amplias de gráficos, incluidos los gráficos cordales ^[11] y los gráficos de ancho de camarilla acotado . ^[12] La última clase incluye cografos y gráficos de ancho de árbol acotado , como los gráficos planos exteriores .

Deleción-contracción

La recurrencia de supresión-contracción proporciona una forma de calcular el polinomio cromático, llamado algoritmo de supresión-contracción . En la primera forma (con un signo menos), la recurrencia termina en una colección de grafos vacíos. En la segunda forma (con un signo más), termina en una colección de grafos completos. Esto forma la base de muchos algoritmos para colorear grafos. La función ChromaticPolynomial en el paquete Combinatorica del sistema de álgebra computacional Mathematica usa la segunda recurrencia si el grafo es denso, y la primera recurrencia si el grafo es disperso. ^[13] El tiempo de ejecución en el peor caso de cualquiera de las fórmulas satisface la misma relación de recurrencia que los números de Fibonacci , por lo que en el peor caso, el algoritmo se ejecuta en el tiempo dentro de un factor polinomial de

${\displaystyle \varphi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),}$

en un gráfico con n vértices y m aristas. ^[14] El análisis se puede mejorar hasta un factor polinomial del número de árboles de expansión del gráfico de entrada. ^[15] En la práctica, se emplean estrategias de ramificación y acotación y rechazo del isomorfismo gráfico para evitar algunas llamadas recursivas, el tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices. ${\displaystyle t(G)}$

Método del cubo

Existe una perspectiva geométrica natural sobre las coloraciones de los grafos al observar que, como una asignación de números naturales a cada vértice, una coloración de grafo es un vector en la red de enteros. Dado que dos vértices y reciben el mismo color es equivalente a que las coordenadas 'th y 'th en el vector de coloración sean iguales, cada arista se puede asociar con un hiperplano de la forma . La colección de tales hiperplanos para un grafo dado se llama su disposición gráfica . Las coloraciones adecuadas de un grafo son aquellos puntos de la red que evitan los hiperplanos prohibidos. Restringiendo a un conjunto de colores, los puntos de la red están contenidos en el cubo . En este contexto, el polinomio cromático cuenta el número de puntos de la red en el -cubo que evitan la disposición gráfica. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \{x\in \mathbb {R} ^{d}:x_{i}=x_{j}\}}$ ${\displaystyle k}$ ${\displaystyle [0,k]^{n}}$ ${\displaystyle [0,k]}$

Complejidad computacional

El problema de calcular el número de 3-coloraciones de un grafo dado es un ejemplo canónico de un problema #P -completo, por lo que el problema de calcular los coeficientes del polinomio cromático es #P-difícil. De manera similar, evaluar para G dado es #P-completo. Por otro lado, para es fácil calcular , por lo que los problemas correspondientes son computables en tiempo polinomial. Para los números enteros, el problema es #P-difícil, lo que se establece de manera similar al caso . De hecho, se sabe que es #P-difícil para todo x (incluidos los números enteros negativos e incluso todos los números complejos ) excepto para los tres "puntos fáciles". ^[16] Por lo tanto, desde la perspectiva de la #P-dureza, la complejidad de calcular el polinomio cromático se entiende completamente. ${\displaystyle P(G,3)}$ ${\displaystyle k=0,1,2}$ ${\displaystyle P(G,k)}$ ${\displaystyle k>3}$ ${\displaystyle k=3}$ ${\displaystyle P(G,x)}$

En la expansión

${\displaystyle P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},}$

El coeficiente siempre es igual a 1 y se conocen otras propiedades de los coeficientes. Esto plantea la cuestión de si algunos de los coeficientes son fáciles de calcular. Sin embargo, el problema computacional de calcular un _r para un r fijo ≥ 1 y un gráfico G dado es #P-hard, incluso para gráficos planares bipartitos. ^[17] ${\displaystyle a_{n}}$

No se conocen algoritmos de aproximación para el cálculo de ningún x excepto para los tres puntos fáciles. En los puntos enteros , el problema de decisión correspondiente de decidir si un gráfico dado puede ser k -coloreado es NP-duro . Tales problemas no pueden aproximarse a ningún factor multiplicativo mediante un algoritmo probabilístico de error acotado a menos que NP = RP, porque cualquier aproximación multiplicativa distinguiría los valores 0 y 1, resolviendo efectivamente la versión de decisión en tiempo polinomial probabilístico de error acotado. En particular, bajo el mismo supuesto, esto descarta la posibilidad de un esquema de aproximación aleatoria de tiempo completamente polinomial (FPRAS) . No hay FPRAS para el cálculo para ningún x > 2, a menos que se cumpla NP  =  RP . ^[18] ${\displaystyle P(G,x)}$ ${\displaystyle k=3,4,\ldots }$ ${\displaystyle P(G,x)}$

Véase también

• Función simétrica cromática

Notas

1. Leer (1968)
2. Varios capítulos Biggs (1993)
3. Dong, Koh y Teo (2005)
4. Stanley (1973)
5. Ellis-Monaghan y Merino (2011)
6. ¿Eh? (2012)
7. Chao y Whitehead (1978)
8. Jackson (1993)
9. Sokal (2004)
10. Helme-Guizon y Rong (2005)
11. Naor, Naor y Schaffer (1987).
12. Giménez, Hliněný y Noy (2005); Makowsky et al. (2006).
13. Pemmaraju y Skiena (2003)
14. Wilf (1986)
15. Sekine, Imai y Tani (1995)
16. Jaeger, Vertigan y Welsh (1990), basado en una reducción en (Linial 1986).
17. Oxley y Welsh (2002)
18. Goldberg y Jerrum (2008)

Referencias

• Biggs, N. (1993), Teoría de grafos algebraicos , Cambridge University Press, ISBN 978-0-521-45897-9
• Chao, C.-Y.; Whitehead, EG (1978), "Sobre la equivalencia cromática de grafos", Teoría y aplicaciones de grafos , Lecture Notes in Mathematics, vol. 642, Springer, págs. 121–131, ISBN 978-3-540-08666-6
• Dong, FM; Koh, KM; Teo, KL (2005), Polinomios cromáticos y cromaticidad de gráficos , World Scientific Publishing Company, ISBN 978-981-256-317-0
• Ellis-Monaghan, Joanna A. ; Merino, Criel (2011), "Polinomios de grafos y sus aplicaciones I: El polinomio de Tutte", en Dehmer, Matthias (ed.), Análisis estructural de redes complejas , arXiv : 0803.3079 , doi :10.1007/978-0-8176-4789-6_9, ISBN 978-0-8176-4789-6, S2CID  585250
• Giménez, O.; Hliněný, P.; Noy, M. (2005), "Cálculo del polinomio de Tutte en grafos de ancho de camarilla acotado", Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005) , Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp. 59–68, CiteSeerX  10.1.1.353.6385 , doi :10.1007/11604686_6, ISBN 978-3-540-31000-6
• Goldberg, LA ; Jerrum, M. (2008), "Inaproximabilidad del polinomio de Tutte", Información y computación , 206 (7): 908, arXiv : cs/0605140 , doi :10.1016/j.ic.2008.04.003, S2CID  53304001
• Helme-Guizon, Laure; Rong, Yongwu (2005), "Una categorización del polinomio cromático", Topología algebraica y geométrica , 5 (4): 1365–1388, arXiv : math/0412264 , doi :10.2140/agt.2005.5.1365, S2CID  1339633
• Huh, June (2012), "Números de Milnor de hipersuperficies proyectivas y el polinomio cromático de grafos", Journal of the American Mathematical Society , 25 (3): 907–927, arXiv : 1008.4749 , doi :10.1090/S0894-0347-2012-00731-0, MR  2904577, S2CID  13523955
• Jackson, B. (1993), "Un intervalo sin ceros para polinomios cromáticos de gráficos", Combinatorics, Probability and Computing , 2 (3): 325–336, doi :10.1017/S0963548300000705, S2CID  39978844
• Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode :1990MPCPS.108...35J, doi :10.1017/S0305004100068936, S2CID  121454726
• Linial, N. (1986), "Problemas de enumeración difíciles en geometría y combinatoria", SIAM J. Algebr. Discrete Methods , 7 (2): 331–335, doi :10.1137/0607036
• Makowsky, JA; Rotics, U.; Averbouch, I.; Godlin, B. (2006), "Cálculo de polinomios de grafos en grafos de ancho de camarilla acotado", Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006) , Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, págs. 191–204, CiteSeerX  10.1.1.76.2320 , doi :10.1007/11917496_18, ISBN 978-3-540-48381-6
• Naor, J.; Naor, M.; Schaffer, A. (1987), "Algoritmos paralelos rápidos para gráficos cordales", Proc. XIX Simposio ACM. Teoría de la Computación (STOC '87) , págs. 355–364, doi : 10.1145/28395.28433 , ISBN 978-0897912211, Número de identificación del sujeto  12132229.
• Oxley, JG; Welsh, DJA (2002), "Polinomios cromáticos, de flujo y de confiabilidad: la complejidad de sus coeficientes", Combinatorics, Probability and Computing , 11 (4): 403–426, doi :10.1017/S0963548302005175, S2CID  14918970
• Pemmaraju, S.; Skiena, S. (2003), Matemáticas discretas computacionales: combinatoria y teoría de grafos con Mathematica , Cambridge University Press, sección 7.4.2, ISBN 978-0-521-80686-2
• Read, RC (1968), "Introducción a los polinomios cromáticos" (PDF) , Journal of Combinatorial Theory , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Cálculo del polinomio de Tutte de un grafo de tamaño moderado", en Staples, John; Eades, Peter; Katoh, Naoki; Moffat, Alistair (eds.), Algorithms and Computation, 6.º Simposio Internacional, ISAAC '95, Cairns, Australia, 4-6 de diciembre de 1995, Actas , Lecture Notes in Computer Science, vol. 1004, Springer, págs. 224-233, doi :10.1007/BFb0015427, ISBN 978-3-540-60573-7
• Sokal, AD (2004), "Las raíces cromáticas son densas en todo el plano complejo", Combinatorics, Probability and Computing , 13 (2): 221–261, arXiv : cond-mat/0012369 , doi :10.1017/S0963548303006023, S2CID  5549332
• Stanley, RP (1973), "Orientaciones acíclicas de gráficos" (PDF) , Discrete Math. , 5 (2): 171–178, doi :10.1016/0012-365X(73)90108-8
• Voloshin, Vitaly I. (2002), Coloración de hipergrafos mixtos: teoría, algoritmos y aplicaciones. , American Mathematical Society, ISBN 978-0-8218-2812-0
• Wilf, HS (1986), Algoritmos y complejidad , Prentice–Hall, ISBN 978-0-13-021973-2

Enlaces externos

• Weisstein, Eric W. , "Polinomio cromático", MathWorld
• Polinomio cromático de PlanetMath Archivado el 20 de agosto de 2008 en Wayback Machine
• Código para calcular polinomios de Tutte, cromáticos y de flujo de Gary Haggard, David J. Pearce y Gordon Royle: [1]