Coloración gráfica

Asignación de colores a elementos de un gráfico sujeto a determinadas limitaciones.

No confundir con la coloración Edge .

Una coloración de vértice adecuada del gráfico de Petersen con 3 colores, el número mínimo posible.

En teoría de grafos , la coloración de grafos es un caso especial de etiquetado de grafos ; es una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de manera que no haya dos vértices adyacentes del mismo color; esto se llama coloración de vértices . De manera similar, un color de borde asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y un color de cara de un gráfico plano asigna un color a cada cara o región para que no haya dos caras que compartan un límite con el mismo color. el mismo color.

La coloración de vértices se usa generalmente para introducir problemas de coloración de gráficos, ya que otros problemas de coloración se pueden transformar en una instancia de coloración de vértices. Por ejemplo, una coloración de borde de un gráfico es solo una coloración de vértice de su gráfico lineal , y una coloración de cara de un gráfico plano es solo una coloración de vértice de su dual . Sin embargo, los problemas de coloración sin vértices a menudo se plantean y estudian tal cual. Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma sin vértice, como en el caso de la coloración de bordes.

La convención de usar colores se origina en colorear los países de un mapa , donde cada cara está literalmente coloreada. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana se convirtió en colorear los vértices, y de esta forma se generaliza a todos los gráficos. En las representaciones matemáticas y de computadora, es típico usar los primeros números enteros positivos o no negativos como los "colores". En general, se puede utilizar cualquier conjunto finito como "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores, pero no de cuáles son.

La coloración de gráficos disfruta de muchas aplicaciones prácticas, así como desafíos teóricos. Además de los tipos clásicos de problemas, también se pueden establecer diferentes limitaciones en el gráfico, o en la forma en que se asigna un color, o incluso en el color en sí. Incluso ha alcanzado popularidad entre el público en general en forma del popular rompecabezas numérico Sudoku . La coloración de gráficos sigue siendo un campo de investigación muy activo.

Nota: Muchos de los términos utilizados en este artículo se definen en el Glosario de teoría de grafos .

Historia

Ver también: Historia del teorema de los cuatro colores e Historia de la teoría de grafos

Los primeros resultados sobre la coloración de gráficos tratan casi exclusivamente de gráficos planos en forma de coloración de mapas . Mientras trataba de colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de los cuatro colores , y señaló que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera un borde común recibiera el mismo color. El hermano de Guthrie pasó la pregunta a su profesor de matemáticas Augustus de Morgan en el University College , quien lo mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la London Mathematical Society.en 1879. El mismo año, Alfred Kempe publicó un artículo que pretendía establecer el resultado, y durante una década se consideró resuelto el problema de los cuatro colores. Por su logro, Kempe fue elegido miembro de la Royal Society y más tarde presidente de la London Mathematical Society. ^[1]

En 1890, Heawood señaló que el argumento de Kempe estaba equivocado. Sin embargo, en ese artículo demostró el teorema de los cinco colores , diciendo que cada mapa plano puede colorearse con no más de cinco colores, usando ideas de Kempe. En el siglo siguiente, se desarrollaron una gran cantidad de trabajo y teorías para reducir el número de colores a cuatro, hasta que el teorema de los cuatro colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken . La prueba se remonta a las ideas de Heawood y Kempe y en gran medida ignora los desarrollos intermedios. ^[2] La prueba del teorema de los cuatro colores también es digna de mención por ser la primera prueba importante asistida por computadora.

En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar los problemas de coloración, que fue generalizado al polinomio de Tutte por Tutte , estructuras importantes en la teoría de grafos algebraicos . Kempe ya había llamado la atención sobre el caso general no plano en 1879, ^[3] y muchos resultados sobre generalizaciones de coloración de gráficos planos a superficies de orden superior siguieron a principios del siglo XX.

En 1960, Claude Berge formuló otra conjetura sobre la coloración de grafos, la conjetura de grafos perfectos fuertes , originalmente motivada por un concepto teórico de la información llamado capacidad de error cero de un grafo introducido por Shannon . La conjetura quedó sin resolver durante 40 años, hasta que se estableció como el célebre teorema fuerte perfecta gráfico por Chudnovsky , Robertson , Seymour , y Thomas en 2002.

La coloración de gráficos se ha estudiado como un problema algorítmico desde principios de la década de 1970: el problema del número cromático (ver más abajo ) es uno de los 21 problemas NP-completos de Karp de 1972, y aproximadamente al mismo tiempo se desarrollaron varios algoritmos de tiempo exponencial basados ​​en el retroceso y sobre la recurrencia de deleción-contracción de Zykov (1949) . Una de las principales aplicaciones de la coloración de gráficos, la asignación de registros en compiladores, se introdujo en 1981.

Definición y terminología

Este gráfico puede tener 3 colores de 12 formas diferentes.

Coloración de vértice

Cuando se usa sin ninguna calificación, la coloración de un gráfico es casi siempre una coloración de vértice adecuada , es decir, un etiquetado de los vértices del gráfico con colores de manera que no haya dos vértices que compartan el mismo borde que tengan el mismo color. Dado que un vértice con un bucle (es decir, una conexión directamente a sí mismo) nunca podría colorearse correctamente, se entiende que los gráficos en este contexto no tienen bucle.

La terminología del uso de colores para las etiquetas de los vértices se remonta a la coloración del mapa. Las etiquetas como rojo y azul solo se usan cuando el número de colores es pequeño, y normalmente se entiende que las etiquetas se extraen de los números enteros {1, 2, 3, ...}.

Una coloración utilizando en la mayoría de k colores se llama un (adecuado) k -Coloreado . La menor cantidad de colores necesarios para colorear un gráfico G se denomina número cromático y, a menudo, se denota χ ( G ). A veces se usa γ ( G ), ya que χ ( G ) también se usa para denotar la característica de Euler de un gráfico. Un gráfico al que se le puede asignar un color k (adecuado) es k -colorable , y es k -cromático si su número cromático es exactamente k . Un subconjunto de vértices asignados al mismo color se llama clase de color. , cada una de estas clases forma un conjunto independiente . Por tanto, un k- colorear es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partite y k-colorable tienen el mismo significado.

Polinomio cromático

Todos los gráficos no isomorfos en 3 vértices y sus polinomios cromáticos. El gráfico vacío E ₃ (rojo) admite una coloración 1; los otros admiten ^{[ aclaración necesaria ]}

Artículo principal: polinomio cromático

El polinomio cromático cuenta el número de formas en que se puede colorear un gráfico utilizando algunos de un número determinado de colores. Por ejemplo, con tres colores, el gráfico de la imagen adyacente se puede colorear de 12 formas. Con solo dos colores, no se puede colorear en absoluto. Con cuatro colores, se puede colorear de 24 + 4⋅12 = 72 formas: ¡usando los cuatro colores, hay 4! = 24 coloraciones válidas ( cada asignación de cuatro colores a cualquier gráfico de 4 vértices es una coloración adecuada); y por cada elección de tres de los cuatro colores, hay 12 3 colores válidos. Entonces, para el gráfico del ejemplo, una tabla del número de colorantes válidos comenzaría así:

Colores disponibles	1	2	3	4	...
Numero de colorantes	0	0	12	72	...

El polinomio cromático es una función que cuenta el número de t- coloraciones de . Como su nombre lo indica, para un dado, la función es de hecho un polinomio en . Para el gráfico de ejemplo , y de hecho .${\displaystyle P(G,t)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle t}$${\displaystyle P(G,t)=t(t-1)^{2}(t-2)}$${\displaystyle P(G,4)=72}$

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

${\displaystyle \chi (G)=\min\{k\,\colon \,P(G,k)>0\}.}$

Polinomios cromáticos para ciertos gráficos

Triángulo K 3	${\displaystyle t(t-1)(t-2)}$
Gráfico completo K n	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
Árbol con n vértices	${\displaystyle t(t-1)^{n-1}}$
Ciclo C n	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Gráfico de Petersen	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Coloración de bordes

Artículo principal: Coloración de bordes

Una coloración de los bordes de un gráfico es una coloración adecuada de los bordes , es decir, una asignación de colores a los bordes para que ningún vértice incida sobre dos bordes del mismo color. Una coloración de aristas con k colores se denomina k -coloración de aristas y es equivalente al problema de dividir el conjunto de aristas en k emparejamientos . El menor número de colores necesarios para la coloración del borde de un gráfico G es el índice cromático , o número cromático del borde , χ ′ ( G ). Una coloración de Tait es una coloración de 3 bordes de un gráfico cúbico . ElEl teorema de los cuatro colores es equivalente a la afirmación de que cada grafo cúbico plano sin puentes admite una coloración de Tait.

Coloración total

Artículo principal: coloración total

La coloración total es un tipo de coloración en los vértices y los bordes de un gráfico. Cuando se usa sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que no se asigna el mismo color a ningún vértice adyacente, ni a ningún borde adyacente, ni a ningún borde y sus vértices finales. El número cromático total χ ″ (G) de un gráfico G es la menor cantidad de colores necesarios en cualquier coloración total de G.

Colorante sin etiqueta

Una coloración sin etiqueta de un gráfico es la órbita de una coloración bajo la acción del grupo de automorfismos del gráfico. Tenga en cuenta que los colores permanecen etiquetados; es el gráfico que no está etiquetado. Existe un análogo del polinomio cromático que cuenta el número de coloraciones sin etiquetar de un gráfico de un conjunto de colores finito dado.

Si interpretamos la coloración de un gráfico en vértices como un vector en , la acción de un automorfismo es una permutación de los coeficientes en el vector de coloración.${\displaystyle d}$${\displaystyle \mathbb {Z} ^{d}}$

Propiedades

Límites superiores del número cromático

Asignar colores distintos a vértices distintos siempre produce una coloración adecuada, por lo que

${\displaystyle 1\leq \chi (G)\leq n.}$

Los únicos gráficos que pueden ser de 1 color son los gráficos sin bordes . Una gráfica completa de n vértices requiere colores. En una coloración óptima, debe haber al menos uno de los m bordes del gráfico entre cada par de clases de color, por lo que${\displaystyle K_{n}}$${\displaystyle \chi (K_{n})=n}$

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

Si G contiene una camarilla de tamaño k , entonces se necesitan al menos k colores para colorear esa camarilla; en otras palabras, el número cromático es al menos el número de camarilla:

${\displaystyle \chi (G)\geq \omega (G).}$

Para gráficos perfectos, este límite es estrecho. Encontrar camarillas se conoce como el problema de las camarillas .

De manera más general, una familia de gráficos está limitada si hay alguna función tal que los gráficos en se pueden colorear con la mayoría de los colores, para la familia de gráficos perfectos, esta función es .${\displaystyle {\mathcal {F}}}$ χ {\displaystyle \chi } ${\displaystyle c}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle c(\omega (G))}$${\displaystyle c(\omega (G))=\omega (G)}$

Los gráficos de 2 colores son exactamente los gráficos bipartitos , incluidos árboles y bosques. Según el teorema de los cuatro colores, cada gráfico plano puede tener 4 colores.

Una coloración codiciosa muestra que cada gráfico se puede colorear con un color más que el grado máximo de vértice ,

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

Los gráficos completos tienen y , y los ciclos impares tienen y , por lo que para estos gráficos este límite es lo mejor posible. En todos los demás casos, el límite se puede mejorar ligeramente; El teorema de Brooks ^[4] establece que${\displaystyle \chi (G)=n}$${\displaystyle \Delta (G)=n-1}$${\displaystyle \chi (G)=3}$${\displaystyle \Delta (G)=2}$

Teorema de Brooks : para un gráfico simple conectado G , a menos que G sea ​​un gráfico completo o un ciclo impar.${\displaystyle \chi (G)\leq \Delta (G)}$

Límites inferiores del número cromático

Se han descubierto varios límites inferiores para los límites cromáticos a lo largo de los años:

Límite de Hoffman: Sea una matriz simétrica real tal que siempre que no sea un borde . Defina dónde están los valores propios más grandes y más pequeños de . Defina , con como arriba. Luego:${\displaystyle W}$${\displaystyle W_{i,j}=0}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$${\displaystyle W}$${\displaystyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$${\displaystyle W}$

${\displaystyle \chi _{H}(G)\leq \chi (G)}$.

Número cromático vectorial :Seauna matriz semidefinida positiva tal quesiemprequehaya una arista en. Definacomo el mínimo k para el queexistetal matriz. Luego${\displaystyle W}$${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{V}(G)}$${\displaystyle W}$

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

Número de Lovász : El número de Lovász de un gráfico complementario también es un límite inferior del número cromático:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

Número cromático fraccionario : el número cromático fraccionario de un gráfico es también un límite inferior del número cromático:

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

Estos límites están ordenados de la siguiente manera:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

Gráficos con alto número cromático

Los gráficos con grandes camarillas tienen un alto número cromático, pero no ocurre lo contrario. El gráfico de Grötzsch es un ejemplo de un gráfico de 4 cromáticos sin triángulo, y el ejemplo se puede generalizar a los Mycielskianos .

Teorema ( William T. Tutte  1947 , ^[5] Alexander Zykov  1949 , Jan Mycielski  1955 ): Existen gráficos sin triángulos con un número cromático arbitrariamente alto.

Para probar esto, tanto Mycielski como Zykov, cada uno dio una construcción de una familia definida inductivamente de gráficos libres de triángulos pero con un número cromático arbitrariamente grande. ^[6] Burling (1965) ^[7] construyó cuadros alineados con el eje en cuyo gráfico de intersección no hay triángulos y requiere arbitrariamente muchos colores para colorear correctamente. Esta familia de gráficos se llama entonces gráficos de Burling. La misma clase de gráficos se usa para la construcción de una familia de segmentos de línea sin triángulos en el plano, dada por Pawlik et. Alabama. (2014). ^[8] Muestra que el número cromático de su gráfico de intersección también es arbitrariamente grande. Por lo tanto, esto implica que los cuadros alineados con el eje en${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$así como los segmentos de línea en no están delimitados por χ . ^[8]${\displaystyle \mathbb {R} ^{2}}$

Según el teorema de Brooks, los gráficos con un número cromático alto deben tener un grado máximo alto. Pero la colorabilidad no es un fenómeno completamente local: una gráfica con una circunferencia alta se ve localmente como un árbol, porque todos los ciclos son largos, pero su número cromático no necesita ser 2:

Teorema ( Erdős ): Existen gráficos de circunferencia y número cromático arbitrariamente altos. ^[9]

Límites en el índice cromático

Una coloración de borde de G es una coloración de vértice de su gráfico lineal y viceversa. Por lo tanto,${\displaystyle L(G)}$

${\displaystyle \chi '(G)=\chi (L(G)).}$

Existe una fuerte relación entre la colorabilidad de los bordes y el grado máximo del gráfico . Dado que todas las aristas incidentes al mismo vértice necesitan su propio color, tenemos${\displaystyle \Delta (G)}$

${\displaystyle \chi '(G)\geq \Delta (G).}$

Es más,

Teorema de Kőnig : si G es bipartito.${\displaystyle \chi '(G)=\Delta (G)}$

En general, la relación es incluso más fuerte de lo que da el teorema de Brooks para la coloración de vértices:

Teorema de Vizing: Una gráfica de grado máximotiene un número cromático de bordeo.${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta +1}$

Otras propiedades

Un gráfico tiene un color k si y solo si tiene una orientación acíclica para la cual el camino más largo tiene una longitud como máximo k ; este es el teorema de Gallai-Hasse-Roy-Vitaver ( Nešetřil & Ossona de Mendez 2012 ).

Para los gráficos planos, los colores de los vértices son esencialmente flujos duales a cero en ninguna parte .

Sobre gráficos infinitos, se sabe mucho menos. Los siguientes son dos de los pocos resultados sobre la coloración de gráficos infinitos:

• Si todos los subgrafos finitos de un grafo infinito G son k -colorables, entonces también lo es G , bajo el supuesto del axioma de elección . Este es el teorema de Bruijn-Erdős de de Bruijn & Erdős (1951) .
• Si una gráfica admite una coloración completa n para cada n ≥ n ₀ , admite una coloración completa infinita ( Fawcett 1978 ).

Problemas abiertos

Como se indicó anteriormente, una conjetura de Reed de 1998 es que el valor está esencialmente más cerca del límite inferior, ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

El número cromático del plano , donde dos puntos son adyacentes si tienen una distancia unitaria, se desconoce, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de gráficos incluyen la conjetura de Hadwiger que establece que cada gráfico con el número cromático k tiene un gráfico completo en k vértices como menor , la conjetura de Erdős-Faber-Lovász delimita el número cromático de uniones de gráficos completos que tienen como máximo un vértice en común a cada par, y la conjetura de Albertson que entre k -Gráficos cromáticos los gráficos completos son los que tienen el menornúmero de cruce .

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para los gráficos planos G , el polinomio no tiene ceros en la región . Aunque se sabe que tal polinomio cromático no tiene ceros en la región y eso , su conjetura aún no está resuelta. También sigue siendo un problema sin resolver caracterizar gráficos que tienen el mismo polinomio cromático y determinar qué polinomios son cromáticos.${\displaystyle P(G,t)}$${\displaystyle [4,\infty )}$${\displaystyle [5,\infty )}$${\displaystyle P(G,4)\neq 0}$

Algoritmos

Coloración gráfica
Decisión
Nombre	Graph colorante, colorante vértice, k -Coloreado
Aporte	Grafica G con n vértices. Entero k
Producción	¿ G admite una coloración de vértice adecuada con k colores?
Tiempo de ejecución	O (2 n n ) [10]
Complejidad	NP-completo
Reducción de	3-Satisfacción
Garey – Johnson	GT4
Mejoramiento
Nombre	Número cromático
Aporte	Grafica G con n vértices.
Producción	χ ( G )
Complejidad	NP-duro
Aproximabilidad	O ( n  (log n ) −3 (log log n ) 2 )
Inaproximabilidad	O ( n 1 − ε ) a menos que P = NP
Problema de conteo
Nombre	Polinomio cromático
Aporte	Grafica G con n vértices. Entero k
Producción	El número P  ( G , k ) de los colores k apropiados de G
Tiempo de ejecución	O (2 n n )
Complejidad	# P-completo
Aproximabilidad	FPRAS para casos restringidos
Inaproximabilidad	Sin PTAS a menos que P = NP

Tiempo polinomial

Determinar si un gráfico se puede colorear con 2 colores es equivalente a determinar si el gráfico es bipartito y, por lo tanto, calculable en tiempo lineal mediante la búsqueda en amplitud o en profundidad . De manera más general, el número cromático y la coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinomial utilizando programación semidefinida . Las fórmulas cerradas para polinomios cromáticos se conocen para muchas clases de gráficos, como bosques, gráficos de cuerdas, ciclos, ruedas y escaleras, por lo que estos se pueden evaluar en tiempo polinomial.

Si el gráfico es plano y tiene un ancho de rama bajo (o no es plano pero con una descomposición de rama conocida), entonces se puede resolver en tiempo polinomial usando programación dinámica. En general, el tiempo requerido es polinomial en el tamaño del gráfico, pero exponencial en el ancho de la rama.

Algoritmos exactos

Búsqueda de fuerza bruta para un k -Coloreado considera cada una de las asignaciones de k colores a n vértices y cheques para cada si es legal. Para calcular el número cromático y el polinomio cromático, este procedimiento se utiliza para todos , poco práctico para todos los gráficos de entrada excepto los más pequeños.${\displaystyle k^{n}}$${\displaystyle k=1,\ldots ,n-1}$

Utilizando la programación dinámica y un límite en el número de conjuntos independientes máximos , la k -colorabilidad se puede decidir en el tiempo y el espacio . ^[11] Utilizando el principio de inclusión-exclusión y el algoritmo de Yates para la transformada zeta rápida, la k -colorabilidad se puede decidir en el tiempo ^[10] para cualquier k . Los algoritmos más rápidos son conocidos por sus 3 y 4 colores, que pueden decidirse en el tiempo ^[12] y , ^[13] respectivamente.${\displaystyle O(2.4423^{n})}$${\displaystyle O(2^{n}n)}$${\displaystyle O(1.3289^{n})}$${\displaystyle O(1.7272^{n})}$

Contracción

La contracción de una gráfica G es la gráfica que se obtiene al identificar los vértices u y v , y eliminar los bordes entre ellos. Los bordes restantes originalmente incidentes con u o v ahora inciden en su identificación. Esta operación juega un papel importante en el análisis de la coloración de gráficos.${\displaystyle G/uv}$

El número cromático satisface la relación de recurrencia :

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

debido a Zykov (1949) , donde u y v son vértices no adyacentes, y es la gráfica con el borde uv añadido. Varios algoritmos se basan en evaluar esta recurrencia y el árbol de cálculo resultante a veces se denomina árbol de Zykov. El tiempo de ejecución se basa en una heurística para elegir los vértices u y v .${\displaystyle G+uv}$

El polinomio cromático satisface la siguiente relación de recurrencia

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

donde u y v son vértices adyacentes, y es la gráfica con el borde uv eliminado. representa el número de posibles coloraciones adecuadas del gráfico, donde los vértices pueden tener el mismo o diferentes colores. Luego, los colores adecuados surgen de dos gráficos diferentes. Para explicar, si los vértices u y v tienen diferentes colores, entonces puede ser que también considere un gráfico donde u y v son adyacentes. Si u y v tienen los mismos colores, también podríamos considerar una gráfica en la que u y v se contraigan. Tutte${\displaystyle G-uv}$${\displaystyle P(G-uv,k)}$La curiosidad por saber qué otras propiedades de los gráficos satisfacían esta recurrencia lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte .

Estas expresiones dan lugar a un procedimiento recursivo llamado algoritmo de eliminación-contracción , que forma la base de muchos algoritmos para colorear gráficos. Los satisface el tiempo de funcionamiento de la misma relación de recurrencia como los números de Fibonacci , por lo que en el peor caso se ejecuta el algoritmo en el tiempo dentro de un factor polinomio de para n vértices y m bordes. ^[14] El análisis se puede mejorar dentro de un factor polinomial del número de árboles de expansión del gráfico de entrada. ^[15] En la práctica, estrategias de ramificación y acotación e isomorfismo de grafos${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$${\displaystyle t(G)}$El rechazo se emplean para evitar algunas llamadas recursivas. El tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices.

Colorear codicioso

Artículo principal: Coloración codiciosa

Dos coloraciones codiciosas del mismo gráfico con diferentes órdenes de vértice. El ejemplo de la derecha se generaliza a gráficos de 2 colores con n vértices, donde el algoritmo codicioso gasta colores.${\displaystyle n/2}$

El algoritmo codicioso considera los vértices en un orden específico ,…, y asigna al color disponible más pequeño no utilizado por los vecinos entre … , agregando un color nuevo si es necesario. La calidad de la coloración resultante depende del orden elegido. Existe un orden que conduce a una coloración codiciosa con el número óptimo de colores. Por otro lado, los colorantes codiciosos pueden ser arbitrariamente malos; por ejemplo, el gráfico de corona en n vértices puede ser de 2 colores, pero tiene un orden que conduce a una coloración codiciosa con colores.${\displaystyle v_{1}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{1}}$${\displaystyle v_{i-1}}$${\displaystyle \chi (G)}$${\displaystyle n/2}$

Para gráficos de cuerdas , y para casos especiales de gráficos de cuerdas, como gráficos de intervalo y gráficos de indiferencia , el algoritmo de coloración codicioso se puede utilizar para encontrar coloraciones óptimas en el tiempo polinomial, eligiendo el orden de vértice para que sea el inverso de un orden de eliminación perfecto para el grafico. Los gráficos perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estos gráficos.

Si los vértices están ordenados según sus grados , la coloración codiciosa resultante utiliza como máximo colores, como máximo uno más que el grado máximo del gráfico. Esta heurística a veces se denomina algoritmo Welsh-Powell. ^[16] Otra heurística debida a Brélaz establece el ordenamiento dinámicamente mientras el algoritmo avanza, eligiendo a continuación el vértice adyacente al mayor número de colores diferentes. ^[17] Muchas otras heurísticas de coloración de gráficos se basan de manera similar en la coloración codiciosa para una estrategia estática o dinámica específica de ordenar los vértices; estos algoritmos a veces se denominan algoritmos de coloración secuencial .${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$

El número máximo (peor) de colores que puede obtenerse mediante el algoritmo codicioso, mediante el uso de un orden de vértices elegido para maximizar este número, se denomina número de Grundy de un gráfico.

Algoritmos paralelos y distribuidos

En el campo de los algoritmos distribuidos , la coloración de gráficos está estrechamente relacionada con el problema de la ruptura de simetría . Los algoritmos aleatorizados de última generación son más rápidos para un grado máximo Δ suficientemente grande que los algoritmos deterministas. Los algoritmos aleatorios más rápidos emplean la técnica de ensayos múltiples de Schneider et al. ^[18]

En un gráfico simétrico , un algoritmo distribuido determinista no puede encontrar un color de vértice adecuado. Se necesita alguna información auxiliar para romper la simetría. Una suposición estándar es que inicialmente cada nodo tiene un identificador único , por ejemplo, del conjunto {1, 2, ..., n }. Dicho de otra manera, asumimos que se nos da un color n . El desafío es reducir el número de colores de n a, por ejemplo, Δ + 1. Cuantos más colores se empleen, por ejemplo, O (Δ) en lugar de Δ + 1, se requieren menos rondas de comunicación. ^[18]

Una versión distribuida sencilla del algoritmo codicioso para colorear (Δ + 1) requiere Θ ( n ) rondas de comunicación en el peor de los casos; es posible que la información deba propagarse de un lado de la red a otro lado.

El caso más simple es un interesante n - ciclo . Richard Cole y Uzi Vishkin ^[19] muestran que existe un algoritmo distribuido que reduce el número de colores de n a O (log  n ) en un paso de comunicación sincrónica. Al iterar el mismo procedimiento, es posible obtener un color de 3 de un ciclo n en pasos de comunicación O ( log *  n ) (asumiendo que tenemos identificadores de nodo únicos).

La función log * , logaritmo iterado , es una función de crecimiento extremadamente lento, "casi constante". Por lo tanto, el resultado de Cole y Vishkin planteó la cuestión de si existe un algoritmo distribuido en tiempo constante para colorear en 3 un ciclo n . Linial (1992) mostró que esto no es posible: cualquier algoritmo distribuido determinista requiere pasos de comunicación Ω ( log *  n ) para reducir un color n a un color 3 en un ciclo n .

La técnica de Cole y Vishkin también se puede aplicar en gráficos arbitrarios de grados acotados; el tiempo de ejecución es poli (Δ) + O ( log *  n ). ^[20] La técnica se extendió a gráficos de discos unitarios por Schneider et al. ^[21] Los algoritmos deterministas más rápidos para colorear (Δ + 1) para Δ pequeños se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. ^[22] El algoritmo de Barenboim et al. se ejecuta en el tiempo O (Δ) +  log * ( n ) / 2, que es óptimo en términos de n ya que el factor constante 1/2 no se puede mejorar debido al límite inferior de Linial.Panconesi y Srinivasan (1996) utilizan descomposiciones de redes para calcular una coloración Δ + 1 en el tiempo .${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$

El problema de la coloración de los bordes también se ha estudiado en el modelo distribuido. Panconesi y Rizzi (2001) logran una coloración (2Δ - 1) en el tiempo O (Δ +  log *  n ) en este modelo. El límite inferior para la coloración de vértices distribuidos debido a Linial (1992) también se aplica al problema de coloración de bordes distribuidos.

Algoritmos descentralizados

Los algoritmos descentralizados son aquellos en los que no se permite el paso de mensajes (a diferencia de los algoritmos distribuidos donde se produce el paso de mensajes locales), y existen algoritmos descentralizados eficientes que colorearán un gráfico si existe un color adecuado. Estos asumen que un vértice es capaz de detectar si alguno de sus vecinos está usando el mismo color que el vértice, es decir, si existe un conflicto local. Esta es una suposición moderada en muchas aplicaciones, por ejemplo, en la asignación de canales inalámbricos, generalmente es razonable suponer que una estación podrá detectar si otros transmisores interferentes están usando el mismo canal (por ejemplo, midiendo la SINR). Esta información de detección es suficiente para permitir que los algoritmos basados ​​en autómatas de aprendizaje encuentren un color gráfico adecuado con probabilidad uno. ^[23]

Complejidad computacional

La coloración de gráficos es computacionalmente difícil. Es NP-completo decidir si un gráfico dado admite un color k para un k dado, excepto en los casos k ∈ {0,1,2}. En particular, es NP-difícil calcular el número cromático. ^[24] El problema de los 3 colores sigue siendo NP-completo incluso en gráficas planas regulares de 4 . ^[25] Sin embargo, para cada k > 3, existe una coloración k de un gráfico plano por el teorema de los cuatro colores , y es posible encontrar dicha coloración en el tiempo polinomial.

El algoritmo de aproximación más conocido calcula una coloración de tamaño como máximo dentro de un factor O ( n (log log  n ) ² (log n) ⁻³ ) del número cromático. ^[26] Para todo ε  > 0, la aproximación del número cromático dentro de n ^{1− ε} es NP-difícil . ^[27]

También es NP-difícil colorear un gráfico de 3 colores con 4 colores ^[28] y un gráfico de k- colores con k ^{(log k  ) / 25} colores para una constante k suficientemente grande . ^[29]

Calcular los coeficientes del polinomio cromático es # P-hard . De hecho, incluso calcular el valor de es # P-difícil en cualquier punto racional k excepto para k  = 1 y k  = 2. ^[30] No existe un FPRAS para evaluar el polinomio cromático en cualquier punto racional k  ≥ 1.5 excepto para k  = 2 a menos que NP  =  RP . ^[31]${\displaystyle \chi (G,k)}$

Para colorear los bordes, la prueba del resultado de Vizing proporciona un algoritmo que utiliza como máximo colores Δ + 1. Sin embargo, decidir entre los dos valores candidatos para el número cromático de borde es NP-completo. ^[32] En términos de algoritmos de aproximación, el algoritmo de Vizing muestra que el número cromático del borde se puede aproximar dentro de 4/3, y el resultado de dureza muestra que no  existe ningún algoritmo (4/3 -  ε ) para ningún ε> 0 a menos que P = NP . Estos se encuentran entre los resultados más antiguos en la literatura sobre algoritmos de aproximación, aunque ninguno de los artículos hace un uso explícito de esa noción. ^[33]

Aplicaciones

Planificación

Modelos de coloración de vértices para una serie de problemas de programación . ^[34] En la forma más limpia, un conjunto determinado de trabajos debe asignarse a intervalos de tiempo, cada trabajo requiere uno de esos intervalos. Los trabajos se pueden programar en cualquier orden, pero los pares de trabajos pueden estar en conflicto en el sentido de que no se pueden asignar al mismo intervalo de tiempo, por ejemplo, porque ambos dependen de un recurso compartido. El gráfico correspondiente contiene un vértice para cada trabajo y una ventaja para cada par de trabajos en conflicto. El número cromático del gráfico es exactamente el intervalo mínimo , el tiempo óptimo para terminar todos los trabajos sin conflictos.

Los detalles del problema de programación definen la estructura del gráfico. Por ejemplo, al asignar aviones a vuelos, el gráfico de conflicto resultante es un gráfico de intervalo , por lo que el problema de coloración se puede resolver de manera eficiente. En la asignación de ancho de banda a las estaciones de radio, el gráfico de conflicto resultante es un gráfico de disco unitario , por lo que el problema de coloración es 3-aproximadamente.

Asignación de registros

Artículo principal: Asignación de registros

Un compilador es un programa informático que traduce un lenguaje informático a otro. Para mejorar el tiempo de ejecución del código resultante, una de las técnicas de optimización del compilador es la asignación de registros , donde los valores más utilizados del programa compilado se guardan en los registros del procesador rápido . Idealmente, los valores se asignan a los registros para que todos puedan residir en los registros cuando se utilicen.

El enfoque de libro de texto para este problema es modelarlo como un problema de coloración de gráficos. ^[35] El compilador construye un gráfico de interferencia , donde los vértices son variables y un borde conecta dos vértices si se necesitan al mismo tiempo. Si el gráfico se puede colorear con k colores, entonces cualquier conjunto de variables necesarias al mismo tiempo se puede almacenar en la mayoría de los k registros.

Otras aplicaciones

El problema de colorear un gráfico surge en muchas áreas prácticas, como la coincidencia de patrones , la programación de deportes, el diseño de planos de asientos, la programación de horarios de exámenes, la programación de taxis y la resolución de acertijos de Sudoku . ^[36]

Otros colorantes

Teoría de Ramsey

Artículo principal: teoría de Ramsey

En la teoría de Ramsey se estudia una clase importante de problemas de coloración inadecuados , donde los bordes del gráfico se asignan a colores y no hay restricción en los colores de los bordes incidentes. Un ejemplo simple es el teorema de la amistad , que establece que en cualquier coloración de las aristas de la gráfica completa de seis vértices, habrá un triángulo monocromático; a menudo se ilustra diciendo que cualquier grupo de seis personas tiene tres extraños mutuos o tres conocidos mutuos. La teoría de Ramsey se preocupa por las generalizaciones de esta idea para buscar la regularidad en medio del desorden, encontrando condiciones generales para la existencia de subgrafos monocromáticos con una estructura dada.${\displaystyle K_{6}}$

Otros colorantes

Coloración total de distinguir vértices adyacentes Una coloración total con la restricción adicional de que dos vértices adyacentes tienen conjuntos de colores diferentes Coloración acíclica Cada subgrafo bicomático es acíclico Coloración B una coloración de los vértices donde cada clase de color contiene un vértice que tiene un vecino en todas las demás clases de color. Coloración circular Motivado por sistemas de tareas en los que la producción se desarrolla de forma cíclica. Cocoloring Una coloración de vértice inadecuada donde cada clase de color induce un conjunto independiente o una camarilla. Coloración completa Cada par de colores aparece en al menos un borde Coloración defectuosa Una coloración de vértice inadecuada donde cada clase de color induce un subgráfico de grado acotado. Coloración distintiva Una coloración de vértice incorrecta que destruye todas las simetrías del gráfico. Coloración equitativa Los tamaños de las clases de colores difieren como máximo en uno. Coloración exacta Cada par de colores aparece exactamente en un borde Coloración fraccionada Los vértices pueden tener varios colores y en cada borde la suma de las partes de color de cada vértice no es mayor que uno. Coloración hamiltoniana Utiliza la longitud de la ruta más larga entre dos vértices, también conocida como distancia de desvío Coloración armoniosa Cada par de colores aparece como máximo en un borde Incidencia colorante Cada incidencia adyacente de vértice y borde está coloreada con colores distintos Coloración de borde de intervalo Un color de los bordes que se encuentran en un vértice común debe ser contiguo Coloración de lista Cada vértice elige de una lista de colores Coloración de bordes de lista Cada borde elige de una lista de colores L (h, k) -coloring La diferencia de colores en los vértices adyacentes es al menos hy la diferencia de colores de los vértices a una distancia dos es al menos k . Un caso particular es la coloración L (2,1) .

Coloración orientada Tiene en cuenta la orientación de los bordes del gráfico. Coloración del camino Modela un problema de enrutamiento en gráficos Radio para colorear La suma de la distancia entre los vértices y la diferencia de sus colores es mayor que k + 1, donde k es un número entero positivo. Coloración de rango Si dos vértices tienen el mismo color i , entonces cada camino entre ellos contiene un vértice con un color mayor que i Subcoloring Una coloración de vértices inadecuada donde cada clase de color induce una unión de camarillas. Suma de coloración El criterio de minimalización es la suma de colores. Coloración de estrellas Cada subgrafo bicomático es una colección inconexa de estrellas Coloración fuerte Cada color aparece en cada partición del mismo tamaño exactamente una vez Fuerte coloración del borde Los bordes están coloreados de manera que cada clase de color induzca una coincidencia (equivalente a colorear el cuadrado del gráfico de líneas) T-coloración El valor absoluto de la diferencia entre dos colores de vértices adyacentes no debe pertenecer al conjunto fijo T Coloración total Los vértices y los bordes están coloreados Coloración centrada Cada subgrafo inducido conectado tiene un color que se usa exactamente una vez Coloración de bordes sin triángulos Los bordes son de color de manera que cada clase de color forma una sin triángulos subgrafo Coloración débil Una coloración de vértice incorrecta donde cada nodo no aislado tiene al menos un vecino con un color diferente

También se puede considerar la coloración para gráficos con signo y gráficos de ganancia .

Ver también

• Gráfico crítico
• Homomorfismo gráfico
• Construcción de Hajós
• Matemáticas del Sudoku
• Gráfico multipartito
• Gráfico de coloración única
• Juego de colorear gráfico

Notas

1. M. Kubale, Historia de la coloración de gráficos , en Kubale (2004)
2. van Lint y Wilson (2001 , Cap. 33)
3. Jensen y Toft (1995) , p. 2
4. Brooks (1941)
5. Descartes, Blanche (abril de 1947), "Un problema de tres colores", Eureka , 21
6. Scott, Alex; Seymour, Paul (2020), "A survey of χ-boundedness", Journal of Graph Theory , 95 (3): 2–3, doi : 10.1002 / jgt.22601.
7. Burling, James Perkins (1965), Sobre problemas de coloración de familias de prototipos (tesis doctoral) , Boulder: Universidad de Colorado.
8. Pawlik, A .; Kozik, J .; Krawczyk, T .; Lasoń, M .; Micek, P .; Trotter, W .; Walczak, B. (2014), "Gráficos de intersección sin triángulos de segmentos de línea con gran número cromático", Journal of Combinatorial Theory , Serie B, 105 (5): 6–10, doi : 10.1016 / j.jctb.2013.11. 001
9. Erdős, Paul (1959), "Teoría de grafos y probabilidad", Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153 / CJM-1959-003-9.
10. Björklund, Husfeldt y Koivisto (2009)
11. Lawler (1976)
12. Beigel y Eppstein (2005)
13. Fomin, Gaspers y Saurabh (2007)
14. Wilf (1986)
15. Sekine, Imai y Tani (1995)
16. Galés y Powell (1967)
17. Brélaz (1979)
18. Schneider (2010)
19. Cole y Vishkin (1986) , véase también Cormen, Leiserson y Rivest (1990 , Sección 30.5)
20. Goldberg, Plotkin y Shannon (1988)
21. Schneider (2008)
22. Barenboim y Elkin (2009) ; Kuhn (2009)
23. Por ejemplo, véanse Leith y Clifford (2006) y Duffy, O'Connell y Sapozhnikov (2008) .
24. Garey, Johnson y Stockmeyer (1974) ; Garey y Johnson (1979) .
25. Dailey (1980)
26. Halldórsson (1993)
27. Zuckerman (2007)
28. Guruswami y Khanna (2000)
29. Khot (2001)
30. Jaeger, Vertigan y Welsh (1990)
31. Goldberg y Jerrum (2008)
32. Holyer (1981)
33. Crescenzi y Kann (1998)
34. Marx (2004)
35. Chaitin (1982)
36. Lewis, R. Una guía para colorear gráficos: algoritmos y aplicaciones . Springer International Publishers, 2015.

Referencias

• Barenboim, L .; Elkin, M. (2009), "Coloración distribuida (Δ + 1) en tiempo lineal (en Δ)", Actas del 41º Simposio de Teoría de la Computación , págs. 111-120, arXiv : 0812.1379 , doi : 10.1145 / 1536414.1536432 , ISBN 978-1-60558-506-2, S2CID  13446345
• Beigel, R .; Eppstein, D. (2005), "3 colores en el tiempo O (1.3289 ⁿ )", Journal of Algorithms , 54 (2)): 168-204, arXiv : cs / 0006046 , doi : 10.1016 / j.jalgor.2004.06 .008 , S2CID  1209067
• Björklund, A .; Husfeldt, T .; Koivisto, M. (2009), "Establecer particiones mediante inclusión-exclusión", SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137 / 070683933
• Brélaz, D. (1979), "Nuevos métodos para colorear los vértices de un gráfico", Comunicaciones del ACM , 22 (4): 251-256, doi : 10.1145 / 359094.359101 , S2CID  14838769
• Brooks, RL (1941), "Sobre colorear los nodos de una red", Proceedings of the Cambridge Philosophical Society , 37 (2): 194-197, Bibcode : 1941PCPS ... 37..194B , doi : 10.1017 / S030500410002168X
• de Bruijn, NG ; Erdős, P. (1951), "Un problema de color para gráficas infinitas y un problema en la teoría de relaciones" (PDF) , Nederl. Akad. Wetensch. Proc. Ser. A , 54 : 371–373, doi : 10.1016 / S1385-7258 (51) 50053-7 , archivado desde el original (PDF) el 2016-03-10 , consultado el 2009-05-16(= Indag. Math. 13 )
• Byskov, JM (2004), "Enumeración de conjuntos independientes máximos con aplicaciones para colorear gráficos", Operations Research Letters , 32 (6): 547–556, doi : 10.1016 / j.orl.2004.03.002

• Chaitin, GJ (1982), "Asignación y derrame de registros mediante coloración de gráficos", Proc. 1982 Simposio SIGPLAN sobre construcción de compiladores , págs. 98–105, doi : 10.1145 / 800230.806984 , ISBN 0-89791-074-5, S2CID  16872867
• Cole, R .; Vishkin, U. (1986), "Lanzamiento de moneda determinista con aplicaciones para la clasificación de lista paralela óptima", Información y control , 70 (1): 32-53, doi : 10.1016 / S0019-9958 (86) 80023-7
• Cormen, TH; Leiserson, CE; Rivest, RL (1990), Introducción a los algoritmos (1ª ed.), The MIT Press
• Crescenzi, P .; Kann, V. (diciembre de 1998), "Cómo encontrar los mejores resultados de aproximación: un seguimiento de Garey y Johnson", ACM SIGACT News , 29 (4): 90, doi : 10.1145 / 306198.306210 , S2CID  15748200
• Dailey, DP (1980), "La unicidad de la colorabilidad y la colorabilidad de las gráficas planas de 4 regulares son NP-completas", Discrete Mathematics , 30 (3): 289-293, doi : 10.1016 / 0012-365X (80) 90236-8
• Duffy, K .; O'Connell, N .; Sapozhnikov, A. (2008), "Análisis de complejidad de un algoritmo de coloración de gráficos descentralizado" (PDF) , Information Processing Letters , 107 (2): 60–63, doi : 10.1016 / j.ipl.2008.01.002
• Fawcett, BW (1978), "Sobre infinitos colores completos de gráficos", Can. J. Math. , 30 (3): 455–457, doi : 10.4153 / cjm-1978-039-8

• Fomin, FV ; Gaspers, S .; Saurabh, S. (2007), "Algoritmos exactos mejorados para contar 3 y 4 colores", Proc. 13a Conferencia Internacional Anual, COCOON 2007 , Lecture Notes in Computer Science , 4598 , Springer, págs. 65–74, doi : 10.1007 / 978-3-540-73545-8_9 , ISBN 978-3-540-73544-1
• Garey, MR ; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 0-7167-1045-5
• Garey, MR ; Johnson, DS ; Stockmeyer, L. (1974), "Algunos problemas NP-completos simplificados", Actas del Sexto Simposio Anual de ACM sobre Teoría de la Computación , págs. 47–63, doi : 10.1145 / 800119.803884 , S2CID  207693360
• Goldberg, LA ; Jerrum, M. (julio de 2008), "Inapproximability of the Tutte polyinomial", Information and Computation , 206 (7): 908–929, arXiv : cs / 0605140 , doi : 10.1016 / j.ic.2008.04.003 , S2CID  53304001
• Goldberg, AV ; Plotkin, SA; Shannon, GE (1988), "Ruptura de simetría paralela en gráficos dispersos" , SIAM Journal on Discrete Mathematics , 1 (4): 434–446, doi : 10.1137 / 0401044
• Guruswami, V .; Khanna, S. (2000), "Sobre la dureza de 4 colores de un gráfico de 3 colores", Actas de la 15ª Conferencia Anual de IEEE sobre Complejidad Computacional , págs. 188-197, doi : 10.1109 / CCC.2000.856749 , ISBN 0-7695-0674-7, S2CID  47551585
• Halldórsson, MM (1993), "Una garantía de rendimiento aún mejor para la coloración aproximada de gráficos", Information Processing Letters , 45 : 19-23, doi : 10.1016 / 0020-0190 (93) 90246-6
• Holyer, I. (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing , 10 (4): 718–720, doi : 10.1137 / 0210055
• Jaeger, F .; Vertigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 108 (1): 35–53, Bibcode : 1990MPCPS.108 ... 35J , doi : 10.1017 / S0305004100068936
• Jensen, TR; Toft, B. (1995), Graph Coloring Problems , Wiley-Interscience, Nueva York, ISBN 0-471-02865-7
• Khot, S. (2001), "Resultados de inaproximabilidad mejorados para MaxClique, número cromático y coloración aproximada del gráfico", Proc. 42º Simposio anual sobre los fundamentos de la informática , págs. 600–609, doi : 10.1109 / SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID  11987483
• Kubale, M. (2004), Coloración de gráficos , American Mathematical Society, ISBN 0-8218-3458-4
• Kuhn, F. (2009), "Colores de gráficos débiles: algoritmos distribuidos y aplicaciones", Actas del 21º Simposio sobre paralelismo en algoritmos y arquitecturas , págs. 138–144, doi : 10.1145 / 1583991.1584032 , ISBN 978-1-60558-606-9, S2CID  8857534
• Lawler, EL (1976), "Una nota sobre la complejidad del problema de los números cromáticos", Information Processing Letters , 5 (3): 66–67, doi : 10.1016 / 0020-0190 (76) 90065-X
• Leith, DJ; Clifford, P. (2006), "Un algoritmo de selección de canal distribuido autogestionado para WLAN", Proc. Rawnet 2006, Boston, MA (PDF) , recuperada 03/03/2016
• Lewis, RMR (2016), A Guide to Graph Coloring: Algorithms and Applications , Springer International Publishing, ISBN 978-3-319-25728-0
• Linial, N. (1992), "Localidad en algoritmos de gráficos distribuidos", SIAM Journal on Computing , 21 (1): 193-201, CiteSeerX  10.1.1.471.6378 , doi : 10.1137 / 0221015
• van Lint, JH; Wilson, RM (2001), Un curso de combinatoria (2a ed.), Cambridge University Press, ISBN 0-521-80340-3
• Marx, Dániel (2004), "Problemas de coloración de gráficos y sus aplicaciones en la programación", Periodica Polytechnica, Ingeniería Eléctrica , 48 , pp. 11-16, CiteSeerX  10.1.1.95.4268
• Mycielski, J. (1955), "Sur le coloriage des graphes" (PDF) , Colloq. Matemáticas. , 3 (2): 161–162, doi : 10.4064 / cm-3-2-161-162.
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Teorema 3.13", Dispersidad: Gráficos, Estructuras y Algoritmos , Algoritmos y Combinatoria, 28 , Heidelberg: Springer, p. 42, doi : 10.1007 / 978-3-642-27875-4 , hdl : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR  2920058.
• Panconesi, Alessandro; Rizzi, Romeo (2001), "Algunos algoritmos distribuidos simples para redes dispersas" (PDF) , Computación distribuida , Berlín, Nueva York: Springer-Verlag , 14 (2): 97–100, doi : 10.1007 / PL00008932 , ISSN  0178- 2770 , S2CID  17661948
• Panconesi, A .; Srinivasan, A. (1996), "Sobre la complejidad de la descomposición de redes distribuidas", Journal of Algorithms , 20
• Sekine, K .; Imai, H .; Tani, S. (1995), "Calcular el polinomio de Tutte de un gráfico de tamaño moderado", Proc. Sexto Simposio Internacional sobre Algoritmos y Computación (ISAAC 1995) , Lecture Notes in Computer Science , 1004 , Springer, págs. 224-233, doi : 10.1007 / BFb0015427 , ISBN 3-540-60573-8
• Schneider, J. (2010), "Una nueva técnica para romper la simetría distribuida" (PDF) , Actas del Simposio sobre Principios de Computación Distribuida
• Schneider, J. (2008), "Un algoritmo de conjunto independiente máximo distribuido en estrella logarítmica para gráficos delimitados por crecimiento" (PDF) , Actas del Simposio sobre principios de computación distribuida
• Galés, DJA; Powell, MB (1967), "Un límite superior para el número cromático de un gráfico y su aplicación a problemas de horarios", The Computer Journal , 10 (1): 85–86, doi : 10.1093 / comjnl / 10.1.85
• West, DB (1996), Introducción a la teoría de grafos , Prentice-Hall, ISBN 0-13-227828-6
• Wilf, HS (1986), Algoritmos y complejidad , Prentice-Hall
• Zuckerman, D. (2007), "Extractores de grado lineal y la inaproximabilidad de Max Clique y el número cromático", Teoría de la Computación , 3 : 103-128, doi : 10.4086 / toc.2007.v003a006
• Zykov, AA (1949), "О некоторых свойствах линейных комплексов" [Sobre algunas propiedades de los complejos lineales], Mat. Sbornik , New Series (en ruso), 24 (66): 163–188, MR  0035428. Traducido al inglés en Amer. Matemáticas. Soc. Traducción , 1952, MR 0051516 .

enlaces externos

Wikimedia Commons tiene medios relacionados con Coloreado de gráficos .

• High-Performance Graph Coloring Algorithms Suite de 8 algoritmos diferentes (implementados en C ++) utilizados en el libro A Guide to Graph Coloring: Algorithms and Applications (Springer International Publishers, 2015).
• Página para colorear de gráficos por Joseph Culberson (programas para colorear de gráficos)
• CoLoRaTiOn de Jim Andrews y Mike Fellows es un rompecabezas para colorear gráficos
• Enlaces a los códigos fuente de Graph Coloring
• Código para calcular eficientemente polinomios de flujo, cromáticos y de Tutte por Gary Haggard, David J. Pearce y Gordon Royle
• Una aplicación web para colorear gráficos de Jose Antonio Martin H.