Coloración de gráficos

Asignación metódica de colores a elementos de un gráfico.

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

En teoría de grafos , la coloración de gráficos es un caso especial de etiquetado de gráficos ; se trata de una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujetos a determinadas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de modo que no haya dos vértices adyacentes del mismo color; esto se llama coloración de vértices . De manera similar, una coloración de aristas asigna un color a cada arista para que no haya dos aristas adyacentes del mismo color, y una coloración de caras 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 utiliza a menudo 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 que no son de 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 utilizar colores tiene su origen en colorear los países de un mapa , donde literalmente se colorea cada cara. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana pasó a colorear los vértices y de esta forma se generaliza a todos los gráficos. En representaciones matemáticas e informáticas, es típico utilizar los primeros números enteros positivos o no negativos como "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 goza de muchas aplicaciones prácticas, así como de desafíos teóricos. Además de los tipos de problemas clásicos, también se pueden establecer diferentes limitaciones en el gráfico, en la forma de asignar un color o incluso en el color mismo. 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 términos utilizados en este artículo se definen en Glosario de teoría de grafos .

Historia

Un mapa de los Estados Unidos que usa colores para mostrar divisiones políticas usando el teorema de los cuatro colores .

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 intentaba colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de los cuatro colores , señalando que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera una frontera común recibiera el mismo color. El hermano de Guthrie transmitió la cuestión a su profesor de matemáticas Augustus De Morgan en el University College , quien la mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la Sociedad Matemática de Londres 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, Percy John Heawood señaló que el argumento de Kempe era erróneo. Sin embargo, en ese artículo demostró el teorema de los cinco colores , diciendo que cada mapa plano se puede colorear con no más de cinco colores, usando ideas de Kempe. En el siglo siguiente, se trabajó mucho y se desarrollaron teorías para reducir el número de colores a cuatro, hasta que Kenneth Appel y Wolfgang Haken demostraron finalmente el teorema de los cuatro colores en 1976 . La prueba se remontaba a las ideas de Heawood y Kempe y ignoraba en gran medida los desarrollos intermedios. ^[2] La prueba del teorema de los cuatro colores es digna de mención, además de su solución a un problema centenario, por ser la primera prueba importante asistida por computadora.

En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar el problema de la coloración, que Tutte generalizó al polinomio de Tutte , ambos invariantes 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 a principios del siglo XX siguieron muchos resultados sobre generalizaciones de la coloración de gráficos planos a superficies de orden superior.

En 1960, Claude Berge formuló otra conjetura sobre la coloración de gráficos, la conjetura fuerte del gráfico perfecto , originalmente motivada por un concepto teórico de la información llamado capacidad de error cero de un gráfico introducido por Shannon . La conjetura permaneció sin resolver durante 40 años, hasta que Chudnovsky, Robertson , Seymour y Thomas la establecieron como el célebre teorema del grafo perfecto fuerte 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 de números cromáticos (consulte la sección #Coloración de vértices a continuación) es uno de los 21 problemas NP completos de Karp de 1972, y aproximadamente al mismo tiempo se desarrollaron varios algoritmos de tiempo exponencial. desarrollado basándose en el retroceso y en 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 los 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értices

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

La terminología del uso de colores para etiquetas de vértices se remonta a la coloración de mapas. Etiquetas como rojo y azul sólo se utilizan 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 que utiliza como máximo k colores se denomina k -coloración (adecuada) . El número más pequeño de colores necesarios para colorear un gráfico G se llama número cromático y, a menudo, se denota por χ( 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 una k -coloración (adecuada) 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 denomina clase de color ; cada una de estas clases forma un conjunto independiente . Por lo tanto, una k -coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k -partito 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; el gráfico completo K ₃ (azul) admite 3 colores; los otros gráficos admiten una coloración bicolor.

El polinomio cromático cuenta la cantidad de formas en que se puede colorear un gráfico usando algunos de un número determinado de colores. Por ejemplo, usando tres colores, el gráfico de la imagen adyacente se puede colorear de 12 maneras. Con sólo dos colores, no se puede colorear en absoluto. Con cuatro colores, se puede colorear de 24 + 4⋅12 = 72 maneras: 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í:

El polinomio cromático es una función P ( G , t ) que cuenta el número de t -coloraciones de G . Como su nombre lo indica, para un G dado la función es de hecho un polinomio en t . Para el gráfico de ejemplo, P ( G , t ) = t ( t – 1) ² ( t – 2) , y de hecho 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 entero positivo más pequeño que no es un cero del polinomio cromático χ( G ) = min{ k  : P ( G , k ) > 0}.

Coloración de bordes

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

coloración total

La coloración total es un tipo de coloración de los vértices y aristas de un gráfico. Cuando se utiliza sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que a ningún vértice adyacente, ni aristas adyacentes, ni a ninguna arista y sus vértices finales se les asigna el mismo color. 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 .

Coloración sin etiqueta

Una coloración sin etiqueta de un gráfico es una órbita de una coloración bajo la acción del grupo de automorfismos del gráfico. Los colores permanecen etiquetados; es el gráfico el 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 finito de colores determinado.

Si interpretamos la coloración de un gráfico en d 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 \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 tener un solo color son los gráficos sin aristas . 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.}$

De manera más general, una familia de gráficos está acotada si existe alguna función tal que los gráficos se puedan 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 gráficos bipartitos , incluidos árboles y bosques. Según el teorema de los cuatro colores, todo 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.}$

Las gráficas completas tienen y y los ciclos impares tienen y , por lo que para estas gráficas este límite es el 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 y 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.

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

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áficas perfectas, este límite es ajustado. Encontrar camarillas se conoce como el problema de las camarillas .

Límite de Hoffman: Sea una matriz simétrica real tal que siempre que no sea una arista en . Defina dónde están los valores propios más grandes y más pequeños de . Defina , como arriba. Entonces: ${\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}$ ${\textstyle \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 quesiempresea una arista en. Definacomo el mínimo k para el que existe dicha matriz. Entonces ${\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 también es 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 camarillas grandes tienen un número cromático elevado, pero no ocurre lo contrario. El gráfico de Grötzsch es un ejemplo de gráfico 4 cromático 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 demostrar esto, tanto Mycielski como Zykov dieron cada uno una construcción de una familia definida inductivamente de gráficos sin triángulos pero con un número cromático arbitrariamente grande. ^[6] Burling (1965) construyó cajas alineadas con ejes en cuyo gráfico de intersección no hay triángulos y requiere muchos colores arbitrarios para colorearse adecuadamente. Esta familia de gráficas se denomina entonces gráficas de Burling. La misma clase de gráficas se utiliza para la construcción de una familia de segmentos de recta sin triángulos en el plano, dada por Pawlik et al. (2014). ^[7] 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 las cajas alineadas con el eje y los segmentos de línea no están acotados por χ . ^[7] ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{2}}$

Según el teorema de Brooks, las gráficas con un número cromático alto deben tener un grado máximo alto. Pero la colorabilidad no es un fenómeno enteramente local: un gráfico con gran circunferencia se parece localmente a un árbol, porque todos los ciclos son largos, pero su número cromático no tiene por qué ser 2:

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

Límites del índice cromático

Una coloración de borde de G es una coloración de vértice de su gráfico lineal , y viceversa. De este modo, ${\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 . Como todas las aristas que inciden en el mismo vértice necesitan su propio color, tenemos ${\displaystyle \Delta (G)}$

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

Además,

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

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

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

Otras propiedades

Un gráfico tiene una coloración 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 y Ossona de Méndez 2012).

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

Acerca de los 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 gráfico infinito G son k -coloreables, entonces G también lo es , bajo el supuesto del axioma de elección . Este es el teorema de Bruijn-Erdős de de Bruijn & Erdős (1951).
• Si un gráfico 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 unidad de distancia, se desconoce, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de gráficas incluyen la conjetura de Hadwiger que establece que toda gráfica con número cromático k tiene un grafo completo en k vértices como menor , la conjetura de Erdős-Faber-Lovász que limita el número cromático de uniones de grafos 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 menor número de cruce .

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para 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 que , su conjetura aún está sin resolver. 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

Tiempo polinomial

Determinar si un gráfico se puede colorear con 2 colores equivale a determinar si el gráfico es bipartito o no y, por lo tanto, computable en tiempo lineal mediante búsqueda en amplitud o búsqueda 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 polinómico utilizando programación semidefinida . Se conocen fórmulas cerradas para polinomios cromáticos para muchas clases de gráficos, como bosques, gráficos cordales, ciclos, ruedas y escaleras, por lo que pueden evaluarse 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 polinómico en el tamaño del gráfico, pero exponencial en el ancho de la rama.

Algoritmos exactos

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

Utilizando 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 . ^[10] Utilizando el principio de inclusión-exclusión y el algoritmo de Yates para la transformada zeta rápida, la colorabilidad k se puede decidir a tiempo ^{[9] [11] [12] [13]} para cualquier k . Se conocen algoritmos más rápidos para la colorabilidad 3 y 4, que se pueden decidir en el tiempo ^[14] y ^[15] respectivamente. Los algoritmos exponencialmente más rápidos también son conocidos por su colorabilidad de 5 y 6, así como por familias restringidas de gráficos, incluidos los gráficos dispersos. ^[dieciséis] ${\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 un gráfico G es el gráfico que se obtiene identificando los vértices u y v y eliminando las aristas entre ellos. Los bordes restantes originalmente incidentes con u o v ahora son incidentes para su identificación ( es decir , el nuevo nodo fusionado uv ). 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 el gráfico con el borde uv agregado. Varios algoritmos se basan en la evaluación de 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 el gráfico sin el borde uv . representa el número de posibles coloraciones propias del gráfico, donde los vértices pueden tener el mismo o diferente color. Entonces las coloraciones adecuadas surgen de dos gráficos diferentes. Para explicarlo, si los vértices u y v tienen colores diferentes, entonces también podríamos considerar una gráfica donde u y v son adyacentes. Si u y v tienen los mismos colores, también podríamos considerar una gráfica donde u y v están contraídos. La curiosidad de Tutte sobre qué otras propiedades gráficas satisfacían esta recurrencia lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte . ${\displaystyle G-uv}$ ${\displaystyle P(G-uv,k)}$

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. El tiempo de ejecución 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 polinómico de para n vértices y m aristas. ^[17] 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. ^[18] En la práctica, se emplean estrategias de rama y límite y rechazo de isomorfismo de gráficos para evitar algunas llamadas recursivas. El tiempo de ejecución depende de la heurística utilizada para seleccionar el par de vértices. ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$ ${\displaystyle t(G)}$

Coloración codiciosa

Dos coloraciones codiciosas del mismo gráfico usando diferentes órdenes de vértices. El ejemplo correcto 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 los asigna al color más pequeño disponible no utilizado por los vecinos entre ,… ,, agregando un color nuevo si es necesario. La calidad de la coloración resultante depende del pedido elegido. Existe un ordenamiento que conduce a una coloración codiciosa con el número óptimo de colores. Por otra parte, los colorantes codiciosos pueden ser arbitrariamente malos; por ejemplo, el gráfico de corona en n vértices puede tener 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 cordales , y para casos especiales de gráficos cordales, como gráficos de intervalos y gráficos de indiferencia , el algoritmo de coloración codiciosa se puede utilizar para encontrar coloraciones óptimas en tiempo polinomial, eligiendo el orden de los vértices como el inverso de un orden de eliminación perfecto para los grafico. Las gráficas perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estas gráficas.

Si los vértices se ordenan 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 de Welsh-Powell. ^[19] 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. ^[20] Muchas otras heurísticas de coloración de gráficos se basan de manera similar en 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 se puede obtener mediante el algoritmo codicioso, utilizando un orden de vértices elegido para maximizar este número, se denomina número de Grundy de un gráfico.

Algoritmos heurísticos

Dos heurísticas de tiempo polinomial bien conocidas para la coloración de gráficos son el algoritmo DSatur y el algoritmo recursivo más grande primero (RLF).

De manera similar al algoritmo de coloración codiciosa , DSatur colorea los vértices de un gráfico uno tras otro, gastando un color no utilizado previamente cuando es necesario. Una vez que se ha coloreado un nuevo vértice , el algoritmo determina cuál de los vértices restantes sin colorear tiene el mayor número de colores diferentes en su vecindad y colorea este vértice a continuación. Esto se define como el grado de saturación de un vértice determinado.

El primer algoritmo recursivo más grande opera de una manera diferente al construir cada clase de color de una en una. Para ello, identifica un conjunto máximo independiente de vértices en el gráfico utilizando reglas heurísticas especializadas. Luego asigna estos vértices al mismo color y los elimina del gráfico. Estas acciones se repiten en el subgrafo restante hasta que no queden vértices.

La complejidad del peor de los casos de DSatur es donde está el número de vértices en el gráfico. El algoritmo también se puede implementar usando un montón binario para almacenar grados de saturación, operando donde está el número de aristas en el gráfico. ^[21] Esto produce ejecuciones mucho más rápidas con gráficos dispersos. La complejidad general de RLF es ligeramente mayor que la de DSatur en . ^[21] ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O((n+m)\log n)}$ ${\displaystyle m}$ ${\displaystyle O(mn)}$

DSatur y RLF son exactos para gráficos bipartitos , de ciclo y de rueda . ^[21]

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 aleatorios 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 y Wattenhofer. ^[22]

En un gráfico simétrico , un algoritmo distribuido determinista no puede encontrar una coloración de vértice adecuada. 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 otro modo, suponemos que se nos da una coloración 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, menos rondas de comunicación se requerirán. ^[22]

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

El caso interesante más simple es un ciclo n . Richard Cole y Uzi Vishkin ^[23] 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 repetir el mismo procedimiento, es posible obtener una coloración triple de un n ciclo en O ( log * n ) pasos de comunicación (suponiendo que tengamos 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 3 en un ciclo n . Linial (1992) demostró que esto no es posible: cualquier algoritmo distribuido determinista requiere Ω ( log *  n ) pasos de comunicación para reducir una n -coloración a una 3-coloración en un n -ciclo.

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 ). ^[24] Schneider y Wattenhofer ampliaron la técnica a gráficos de discos unitarios . ^[25] Los algoritmos deterministas más rápidos para la coloración (Δ + 1) para Δ pequeños se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. ^[26] 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 tiempo O (Δ +  log *  n ) en este modelo. El límite inferior para la coloración distribuida de vértices debido a Linial (1992) se aplica también al problema de coloración distribuida de bordes.

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 realiza el paso de mensajes local), y existen algoritmos descentralizados eficientes que colorearán un gráfico si existe una coloración adecuada. Estos suponen 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 leve 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 que interfieren 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 de gráfico adecuado con probabilidad uno. ^[27]

Complejidad computacional

La coloración de gráficos es computacionalmente difícil. Es NP-completo decidir si un gráfico dado admite una k -coloración para un k dado , excepto en los casos k ∈ {0,1,2} . En particular, es NP-difícil calcular el número cromático. ^[28] El problema de 3 colores sigue siendo NP completo incluso en gráficos planos de 4 regulares . ^[29] Sin embargo, en gráficos con grado máximo 3 o menos, el teorema de Brooks implica que el problema de 3 colores se puede resolver en tiempo lineal. Además, para cada k > 3, existe una k -coloración de un gráfico plano según el teorema de los cuatro colores , y es posible encontrar dicha coloración en tiempo polinomial. Sin embargo, encontrar los 4 colores lexicográficamente más pequeños de un gráfico plano es NP-completo. ^[30]

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. ^[31] Para todo ε  > 0, aproximar el número cromático dentro de n ^{1− ε} es NP-duro . ^[32]

También es NP-difícil colorear un gráfico de 3 colores con 5 colores, ^[33] un gráfico de 4 colores con 7 colores, ^[33] y un gráfico de k colores con colores para k ≥ 5. ^[34] ${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$

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

Para la coloración de bordes, la prueba del resultado de Vizing proporciona un algoritmo que utiliza como máximo Δ+1 colores. Sin embargo, decidir entre los dos valores candidatos para el número cromático del borde es NP-completo. ^[37] 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 cualquier ε > 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 uso explícito de esa noción. ^[38]

Aplicaciones

Planificación

Modelos de coloración de vértices para una serie de problemas de programación . ^[39] En la forma más clara, un conjunto determinado de trabajos debe asignarse a franjas horarias; cada trabajo requiere una de esas franjas horarias. 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 arista para cada par de trabajos en conflicto. El número cromático del gráfico es exactamente el makespan mínimo , el momento ó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 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 aproximado.

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 mantienen en los registros rápidos del procesador . Idealmente, los valores se asignan a los registros para que todos puedan residir en los registros cuando se utilicen.

El enfoque de los libros de texto para este problema es modelarlo como un problema de coloración de gráficos. ^[40] El compilador construye un gráfico de interferencia , donde los vértices son variables y un borde conecta dos vértices si son necesarios 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 como máximo k registros.

Otras aplicaciones

El problema de colorear un gráfico surge en muchas áreas prácticas, como la programación de deportes, ^[41] el diseño de planos de asientos, ^[42] los horarios de exámenes, ^[43] la programación de taxis, ^[44] y la resolución de Sudokus . ^[45]

Otros colorantes

teoría de ramsey

Una clase importante de problemas de coloración inadecuada se estudia en la teoría de Ramsey , donde los bordes del gráfico se asignan a colores y no hay restricción en los colores de los bordes incidentes. Un ejemplo sencillo es el teorema de amigos y extraños , 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 desconocidos en común o tres conocidos en común. La teoría de Ramsey se ocupa de las generalizaciones de esta idea para buscar regularidad en medio del desorden, encontrando condiciones generales para la existencia de subgrafos monocromáticos con una estructura determinada. ${\displaystyle K_{6}}$

Otros colorantes

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

Ver también

• gráfico crítico
• Juego de colorear gráficos
• Homomorfismo gráfico
• construcción hajós
• Matemáticas del Sudoku
• Gráfico multipartito
• Gráfico con colores únicos

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ág. 2.
4. Arroyos (1941).
5. Descartes (1947).
6. Scott y Seymour (2020).
7. Pawlik y col. (2014).
8. Erdős (1959).
9. Björklund, Husfeldt y Koivisto (2009), pág. 550.
10. Leyler (1976).
11. Yates (1937), pág. 66-67.
12. Knuth (1997), Capítulo 4.6.4, págs. 501-502.
13. Koivisto (2004), págs. 45, 96-103.
14. Beigel y Eppstein (2005).
15. Fomin, Gaspers y Saurabh (2007).
16. Zamir (2021).
17. Wilf (1986).
18. Sekine, Imai y Tani (1995).
19. Galés y Powell (1967).
20. Brélaz (1979).
21. Lewis (2021).
22. Schneider y Wattenhofer (2010).
23. Cole y Vishkin (1986), véase también Cormen, Leiserson y Rivest (1990, sección 30.5).
24. Goldberg, Plotkin y Shannon (1988).
25. Schneider y Wattenhofer (2008).
26. Barenboim y Elkin (2009); Kuhn (2009).
27. Véase, por ejemplo, Leith & Clifford (2006) y Duffy, O'Connell & Sapozhnikov (2008).
28. Garey, Johnson y Stockmeyer (1974); Garey y Johnson (1979).
29. Dailey (1980).
30. Khuller y Vazirani (1991).
31. Halldórsson (1993).
32. Zuckerman (2007).
33. Bulín, Krokhin y Opršal (2019).
34. Wrochna y Živný (2020).
35. Jaeger, Vertigan y galés (1990).
36. Goldberg y Jerrum (2008).
37. Más santo (1981).
38. Crescenzi y Kann (1998).
39. Marx (2004).
40. Chaitín (1982).
41. Lewis (2021), págs. 221–246, Capítulo 8: Diseño de ligas deportivas.
42. Lewis (2021), págs. 203–220, Capítulo 7: Diseño de planos de asientos.
43. Lewis (2021), págs. 247–276, Capítulo 9: Diseño de horarios universitarios.
44. Lewis (2021), págs. 5–6, Sección 1.1.3: Programación de taxis.
45. Lewis (2021), págs. 172-179, Sección 6.4: Cuadrados latinos y sudokus.

Referencias

• Barenboim, L.; Elkin, M. (2009), "Coloración distribuida (Δ + 1) en tiempo lineal (en Δ ), Actas del 41º Simposio sobre 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 partición 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", Actas de la Sociedad Filosófica de Cambridge , 37 (2): 194–197, Bibcode :1941PCPS...37..194B, doi :10.1017/S030500410002168X, S2CID  209835194
• de Bruijn, NG ; Erdős, P. (1951), "Un problema de color para gráficos infinitos y un problema de teoría de relaciones" (PDF) , Nederl. Akád. Wetensch. Proc. Ser. A , 54 : 371–373, doi :10.1016/S1385-7258(51)50053-7, archivado desde el original (PDF) el 10 de marzo de 2016 , consultado el 16 de mayo de 2009(= Indag. Matemáticas. 13 )
• Bulín, J.; Krokhin, A.; Opršal, J. (2019), "Enfoque algebraico para prometer satisfacción de restricciones", Actas del 51.º Simposio anual ACM SIGACT sobre teoría de la computación , págs. 602–613, arXiv : 1811.00970 , doi : 10.1145/3313276.3316300
• Burling, James Perkins (1965), Sobre problemas de coloración de familias de prototipos (tesis doctoral), Boulder: Universidad de Colorado
• 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 distribución 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 determinista de monedas con aplicaciones para una clasificación óptima de listas paralelas", 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 singularidad de la colorabilidad y la colorabilidad de los gráficos planos de 4 regulares son NP-completos", Matemáticas discretas , 30 (3): 289–293, doi : 10.1016/0012-365X(80)90236-8
• Descartes, Blanche (abril de 1947), "Un problema de tres colores", Eureka , 21
• 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
• Erdős, Paul (1959), "Teoría de grafos y probabilidad", Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153/CJM-1959-003-9 , S2CID  122784453
• Fawcett, BW (1978), "Sobre la infinita coloración completa de los gráficos", Can. J. Matemáticas. , 30 (3): 455–457, doi : 10.4153/cjm-1978-039-8 , S2CID  123812465
• Fomín, FV ; Gaspers, S.; Saurabh, S. (2007), "Algoritmos exactos mejorados para contar 3 y 4 colores", Proc. 13ª Conferencia Internacional Anual, COCOON 2007 , Apuntes de conferencias sobre informática , vol. 4598, Springer, págs. 65–74, doi : 10.1007/978-3-540-73545-8_9 , ISBN 978-3-540-73544-1
• Garey, señor ; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de la integridad NP , WH Freeman, ISBN 0-7167-1045-5
• Garey, señor ; Johnson, DS ; Stockmeyer, L. (1974), "Algunos problemas NP-completos simplificados", Actas del Sexto Simposio Anual ACM sobre Teoría de la Computación, págs. 47–63, doi :10.1145/800119.803884, ISBN 9781450374231, S2CID  207693360
• Goldberg, Luisiana ; Jerrum, M. (julio de 2008), "Inaproximabilidad del polinomio de Tutte", Información y Computación , 206 (7): 908–929, arXiv : cs/0605140 , doi :10.1016/j.ic.2008.04.003, S2CID  53304001
• Goldberg, AV ; Plotkin, SA; Shannon, GE (1988), "Rotura de simetría paralela en gráficos dispersos", Revista SIAM de Matemáticas Discretas , 1 (4): 434–446, doi :10.1137/0401044
• 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), "La integridad NP de la coloración de bordes", SIAM Journal on Computing , 10 (4): 718–720, doi :10.1137/0210055, S2CID  13131049
• 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
• Jensen, TR; Toft, B. (1995), Problemas de coloración de gráficos , Wiley-Interscience, Nueva York, ISBN 0-471-02865-7
• Khuller, Samir; Vazirani, Vijay V. (30 de septiembre de 1991), "La coloración del gráfico plano no es autorreducible, suponiendo P ≠ NP", Ciencias de la Computación Teórica , 88 (1): 183–189, doi :10.1016/0304-3975 ( 91)90081-C, ISSN  0304-3975
• Knuth, Donald Ervin (1997), Algoritmos seminuméricos , El arte de la programación informática, vol. 2 (3.ª ed.), Lectura/MA: Addison-Wesley, ISBN 0-201-89684-2
• Koivisto, Mikko (enero de 2004), Algoritmos de suma-producto para el análisis de riesgos genéticos (tesis doctoral), Departamento CS Ser. Pub. Una, vol. A-2004-1, Universidad de Helsinki, ISBN 952-10-1578-0
• Kubale, M. (2004), Graph Colorings , Sociedad Matemática Estadounidense, ISBN 0-8218-3458-4
• Kuhn, F. (2009), "Colores de gráficos débiles: algoritmos y aplicaciones distribuidos", 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 canales distribuidos autogestionado para WLAN" (PDF) , Proc. RAWNET 2006, Boston, MA , consultado el 3 de marzo de 2016
• Lewis, RMR (2016), Guía para colorear gráficos: algoritmos y aplicaciones, Springer International Publishing, ISBN 978-3-319-25728-0
• Lewis, RMR (2021), Guía para colorear gráficos, textos de informática, doi :10.1007/978-3-030-81054-2, ISBN 978-3-030-81053-5, S2CID  57188465
• 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 (2ª 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 , vol. 48, págs. 11 a 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", Escasez: gráficos, estructuras y algoritmos , Algoritmos y combinatoria, vol. 28, Heidelberg: Springer, pág. 42, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, señor  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 , vol. 20
• Pawlik, A.; Kozik, J.; Krawczyk, T.; Lasoń, M.; Micek, P.; Trotón, W.; Walczak, B. (2014), "Gráficos de intersección sin triángulos de segmentos de línea con números cromáticos grandes", Journal of Combinatorial Theory , Serie B, 105 (5): 6–10, arXiv : 1209.1595 , doi : 10.1016/j. jctb.2013.11.001
• Scott, Alex; Seymour, Paul (2020), "Un estudio de la acotación de χ ", Journal of Graph Theory , 95 (3): 2–3, doi :10.1002/jgt.22601, S2CID  4760027
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Cálculo del 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 , vol. 1004, Springer, págs. 224–233, doi :10.1007/BFb0015427, ISBN 3-540-60573-8
• Schneider, Johannes; Wattenhofer, Roger (2010), "Una nueva técnica para romper la simetría distribuida", en Richa, Andréa W .; Guerraoui, Rachid (eds.), Actas del 29º Simposio anual de ACM sobre principios de informática distribuida, PODC 2010, Zurich, Suiza, 25 al 28 de julio de 2010, Association for Computing Machinery, págs. 257–266, doi :10.1145/ 1835698.1835760
• Schneider, Johannes; Wattenhofer, Roger (2008), "Un algoritmo de conjunto independiente máximo distribuido en estrella logarítmica para gráficos ligados al crecimiento", en Bazzi, Rida A.; Patt-Shamir, Boaz (eds.), Actas del vigésimo séptimo simposio anual de ACM sobre principios de informática distribuida, PODC 2008, Toronto, Canadá, 18 al 21 de agosto de 2008 , Association for Computing Machinery, págs. doi :10.1145/1400751.1400758
• 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 programación 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
• Wrochna, M.; Živný, S. (2020), "Dureza mejorada para coloraciones H de gráficos coloreables G", Actas del trigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos , págs.
• Yates, F. (1937), El diseño y análisis de experimentos factoriales (Comunicación técnica), vol. 35, Harpenden, Inglaterra: Oficina de Suelos de la Commonwealth
• Zamir, Or (2021), "Rompiendo la barrera de 2 ⁿ para 5 colores y 6 colores", en Bansal, Nikhil; Merelli, Emanuela; Worrell, James (eds.), 48º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) , Actas Internacionales de Leibniz en Informática (LIPIcs), vol. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 113:1–113:20, doi :10.4230/LIPIcs.ICALP.2021.113
• Zuckerman, D. (2007), "Extractores de grados lineales 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 , Nueva Serie (en ruso), 24 (66): 163–188, SEÑOR  0035428. Traducido al inglés en Amer. Matemáticas. Soc. Traducción , 1952, MR 0051516.

enlaces externos

• Algoritmos de coloración de gráficos de alto rendimiento Conjunto de 8 algoritmos diferentes (implementados en C++) utilizados en el libro Una guía para la coloración de gráficos: algoritmos y aplicaciones (Springer International Publishers, 2015).
• Página para colorear de gráficos de Joseph Culberson (programas para colorear de gráficos)
• CoLoRaTiOn de Jim Andrews y Mike Fellows es un rompecabezas para colorear gráficos
• Enlaces a códigos fuente de Graph Coloring
• Código para calcular de manera eficiente polinomios Tutte, cromáticos y de flujo Archivado el 16 de abril de 2008 en Wayback Machine por Gary Haggard, David J. Pearce y Gordon Royle.
• Una aplicación web para colorear gráficos de José Antonio Martín H.