Polinomio cromático

Función en teoría de grafos algebraicos

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

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

Historia

George David Birkhoff introdujo el polinomio cromático en 1912, definiéndolo sólo para gráficas planas , 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 mostrando para todos los gráficos planos G. De esta manera esperaba aplicar las poderosas herramientas del análisis y el álgebra para estudiar las raíces de polinomios al problema de coloración combinatoria. ${\displaystyle P(G,k)}$ ${\displaystyle P(G,4)>0}$

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

Definición

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

Para un gráfico G , cuenta el número de sus k -coloraciones de vértices (adecuados) . Otras notaciones comúnmente utilizadas incluyen , o . Existe un polinomio único que evaluado en cualquier número entero k ≥ 0 coincide con ; se llama 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 gráfico de ruta 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 son diferentes de la elección del segundo vértice. Por tanto, es el número de k -coloraciones de . Para una variable x (no necesariamente entera), tenemos por lo tanto . (Las coloraciones que difieren sólo por permutación de colores o por automorfismos de G todavía 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 deriva de una relación de recurrencia llamada recurrencia de eliminació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 gráfico se obtiene fusionando los dos vértices y eliminando cualquier arista entre ellos. Si y son adyacentes en G , denotemos la gráfica obtenida al eliminar la arista . Entonces los números de k -coloraciones de estos gráficos 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 el borde agregado, 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 los mismos colores. En el primer caso, esto da una coloración k (adecuada) de , mientras que en el segundo caso da una coloración de . Por el contrario, 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}$

Por tanto, el polinomio cromático puede definirse recursivamente como

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

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

Dado que el número de k -coloraciones del gráfico sin aristas es efectivamente , se deduce 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é otras invariantes gráficas 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 menor entero positivo 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 multiplicado por 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 a la invariante cromática 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 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)|}$

Probamos esto mediante inducción sobre el número de aristas en un gráfico simple G con vértices y aristas. Cuando , G es un gráfico vacío. Por lo tanto, por definición . Entonces el coeficiente de es , lo que implica que la afirmación es verdadera para un gráfico vacío. Cuando , como en G tiene una sola arista, . Por tanto, el coeficiente de es . Entonces, el enunciado es válido para k = 1. Utilizando una inducción fuerte, suponga que el enunciado es verdadero para . Dejemos que G tenga 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)}$,

Deja , y . Por eso . Dado que se obtiene de G eliminando solo una arista e , entonces , 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 y elegido arbitrariamente. ^[5] ${\displaystyle x^{1}}$ ${\displaystyle (-1)^{n-1}}$
• Los valores absolutos de los coeficientes de cada polinomio cromático forman una secuencia log-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 k -suma de camarilla de y (es decir, un gráfico obtenido pegando 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 gráficas son cromáticamente equivalentes si tienen el mismo polinomio cromático. Los gráficos isomorfos tienen el mismo polinomio cromático, pero los gráficos 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 gráfico de garra como del gráfico 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, hasta el isomorfismo. En otras palabras, G es cromáticamente único, entonces implicaría que G y H son isomorfos. Todos los gráficos de ciclo 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áficas planas, 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 gráfico puede tener color 0, por lo que 0 es siempre una raíz cromática. Solo los gráficos sin aristas pueden tener 1 color, por lo que 1 es una raíz cromática de cada gráfico con al menos una arista. Por otro lado, salvo estos dos puntos, ninguna gráfica puede tener 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 \phi }$ ${\displaystyle \phi ^{2}}$ ${\displaystyle G_{n}}$

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

Si bien la recta 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]

Colorantes usando todos los colores.

Para un gráfico G en n vértices, denotemos el número de coloraciones usando 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 mediante automorfismos de G todavía se cuentan por separado ). En otras palabras, cuenta el número de particiones del conjunto de vértices en k conjuntos independientes (no vacíos) . Luego cuenta el número de colorantes usando exactamente k colores (con colores distinguibles). Para un número entero x , todas las coloraciones x de G se pueden obtener de forma única eligiendo un número entero k ≤ x , eligiendo k colores a utilizar entre 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 tanto, los números son los coeficientes del polinomio en base a factoriales decrecientes. ${\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 factoriales decrecientes. 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 gráfico dado G ; ${\displaystyle P(G,x)}$
• evaluando en una x fija para G dado . ${\displaystyle P(G,x)}$

El primer problema es más general porque si conociéramos los coeficientes de podríamos evaluarlo en cualquier punto del tiempo polinómico porque el grado es n . La dificultad del segundo tipo de problema depende en gran medida del valor de x y ha sido intensamente estudiado en complejidad computacional . Cuando x es un número natural, este problema normalmente se considera como calcular el número de coloraciones x de una gráfica determinada. Por ejemplo, esto incluye el problema #3: colorear de contar el número de 3 colores, 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 camarillas, como se enumera 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 gráficos cordales ^[11] y 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 externos .

Deleción-contracción

La recurrencia de eliminación-contracción proporciona una forma de calcular el polinomio cromático, llamado algoritmo de eliminación-contracción . En la primera forma (con un signo menos), la recurrencia termina en una colección de gráficos vacíos. En la segunda forma (con un signo más), termina en una colección de gráficos completos. Esto forma la base de muchos algoritmos para colorear gráficos. La función ChromaticPolynomial en el paquete Combinatorica del sistema de álgebra informática Mathematica usa la segunda recurrencia si el gráfico es denso y la primera recurrencia si el gráfico es disperso. ^[13] El tiempo de ejecución en el peor de los casos 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 de los casos, el algoritmo se ejecuta en el tiempo dentro de un factor polinomial de

${\displaystyle \phi ^{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 dentro de un factor polinómico del número de árboles de expansión del gráfico de entrada. ^[15] En la práctica, se emplean estrategias de rama y límite y rechazo de isomorfismo gráfico para evitar algunas llamadas recursivas; el tiempo de ejecución depende de la heurística utilizada para seleccionar el par de vértices. ${\displaystyle t(G)}$

método del cubo

Existe una perspectiva geométrica natural sobre la coloración de gráficos al observar que, como una asignación de números naturales a cada vértice, la coloración de un gráfico es un vector en la red de números enteros. Dado que dos vértices y tener el mismo color equivalen a que las coordenadas 'ésima y 'ésima 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 gráfico dado se llama disposición gráfica . Los colores adecuados de un gráfico son aquellos puntos de la red que evitan los hiperplanos prohibidos. Restringiéndonos 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 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 colores de un gráfico 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, debido a que es fácil de calcular , los problemas correspondientes son computables en tiempo polinomial. Para números enteros el problema es #P-hard, que se establece de forma similar al caso . De hecho, se sabe que es #P-duro para todos los x (incluidos los 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 dureza #P, la complejidad de calcular el polinomio cromático se comprende 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 expansion

${\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 varias 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 ar para un fijo r ≥ 1 y un gráfico dado G es #P-difícil, incluso para gráficos planos bipartitos. ^[17] ${\displaystyle a_{n}}$

No se conocen algoritmos de aproximación para computación para ninguna x excepto para los tres puntos fáciles. En los puntos enteros , el problema de decisión correspondiente a decidir si un gráfico dado puede tener k colores es NP-difícil . Dichos 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 polinómico probabilístico de error acotado. En particular, bajo el mismo supuesto, esto descarta la posibilidad de un esquema de aproximación aleatoria en tiempo totalmente polinomial (FPRAS) . Para otros puntos se necesitan argumentos más complicados y la cuestión es objeto de investigación activa. A partir de 2008 , se sabe que no existe un FPRAS para calcular cualquier x > 2, a menos que se cumpla NP  =  RP . ^[18] ${\displaystyle P(G,x)}$ ${\displaystyle k=3,4,\ldots }$^[update] ${\displaystyle P(G,x)}$

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 & Welsh (1990), basado en una reducción de (Linial 1986).
17. Oxley y galés (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 gráficos", Teoría y aplicaciones de gráficos , 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), "Graficar polinomios 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 gráficas de ancho de camarilla acotado", Proc. 31° Int. Trabajo. Conceptos de teoría de grafos en informática (WG 2005) , Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, págs. 59–68, CiteSeerX  10.1.1.353.6385 , doi :10.1007/11604686_6, ISBN 978-3-540-31000-6
• Goldberg, Luisiana ; 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
• Helmé-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, junio (2012), "Números de Milnor de hipersuperficies proyectivas y el polinomio cromático de gráficos", Journal of the American Mathematical Society , 25 (3): 907–927, arXiv : 1008.4749 , doi : 10.1090/S0894-0347-2012 -00731-0, SEÑOR  2904577, S2CID  13523955
• Jackson, B. (1993), "Un intervalo libre de cero para polinomios cromáticos de gráficos", Combinatoria, probabilidad y computación , 2 (3): 325–336, doi :10.1017/S0963548300000705, S2CID  39978844
• Jaeger, F.; Vértigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Actas matemáticas de la Sociedad Filosófica de Cambridge , 108 (1): 35–53, Bibcode :1990MPCPS.108...35J, doi :10.1017 /S0305004100068936, S2CID  121454726
• Linial, N. (1986), "Problemas difíciles de enumeración en geometría y combinatoria", SIAM J. Algebr. Métodos discretos , 7 (2): 331–335, doi :10.1137/0607036
• Makowsky, JA; Rotics, U.; Averbouch, I.; Godlin, B. (2006), "Cálculo de polinomios de gráficos en gráficos de ancho de camarilla acotado", Proc. 32° Int. Trabajo. Conceptos de teoría de grafos en informática (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, S2CID  12132229.
• Oxley, JG; Welsh, DJA (2002), "Polinomios cromáticos, de flujo y de confiabilidad: la complejidad de sus coeficientes", Combinatoria, probabilidad y computación , 11 (4): 403–426, doi :10.1017/S0963548302005175, S2CID  14918970
• Pemmaraju, S.; Skiena, S. (2003), Matemática discreta computacional: 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), "Una 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 gráfico de tamaño moderado", en Staples, John; Eades, Peter; Katoh, Naoki; Moffat, Alistair (eds.), Algoritmos y Computación, Sexto Simposio Internacional, ISAAC '95, Cairns, Australia, 4 al 6 de diciembre de 1995, Actas , Lecture Notes in Computer Science, vol. 1004, Springer, págs. 224–233, doi :10.1007/BFb0015427
• Sokal, AD (2004), "Las raíces cromáticas son densas en todo el plano complejo", Combinatoria, probabilidad y computación , 13 (2): 221–261, arXiv : cond-mat/0012369 , doi :10.1017/S0963548303006023, S2CID  5549332
• Stanley, RP (1973), "Orientaciones acíclicas de gráficos" (PDF) , Matemáticas discretas. , 5 (2): 171–178, doi :10.1016/0012-365X(73)90108-8
• Voloshin, Vitaly I. (2002), Coloración de hipergrafías mixtas: teoría, algoritmos y aplicaciones. , Sociedad Estadounidense de Matemáticas, 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 PlanetMath Archivado el 20 de agosto de 2008 en la Wayback Machine.
• Código para calcular polinomios Tutte, cromáticos y de flujo por Gary Haggard, David J. Pearce y Gordon Royle: [1]