Coloración de gráficos

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 grafo sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un grafo de manera 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 de manera que no haya dos aristas adyacentes del mismo color, y una coloración de caras de un grafo plano asigna un color a cada cara o región de manera que no haya dos caras que compartan un límite que tengan el mismo color.

La coloración de vértices se utiliza a menudo para introducir problemas de coloración de grafos, 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 aristas de un grafo es simplemente una coloración de vértices de su grafo lineal , y una coloración de caras de un grafo plano es simplemente una coloración de vértices de su dual . Sin embargo, los problemas de coloración sin vértices a menudo se plantean y se estudian tal como están. Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma sin vértices, como en el caso de la coloración de aristas.

La convención de usar colores se origina al 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 planar se convirtió en colorear los vértices, y en 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 usar cualquier conjunto finito como el "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores, pero no de cuáles sean.

La coloración de gráficos tiene muchas aplicaciones prácticas y plantea desafíos teóricos. Además de los tipos clásicos de problemas, también se pueden establecer diferentes limitaciones en el gráfico, en la forma de asignar 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 términos utilizados en este artículo están definidos en el Glosario de teoría de grafos .

Los primeros resultados sobre la coloración de grafos tratan casi exclusivamente de grafos 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 le pasó 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 London Mathematical Society en 1879. El mismo año, Alfred Kempe publicó un artículo que afirmaba establecer el resultado, y durante una década el problema de los cuatro colores se consideró resuelto. 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 puede colorearse con no más de cinco colores, utilizando las ideas de Kempe. En el siglo siguiente, se realizó una gran cantidad de trabajo 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 en gran medida ignoraba los desarrollos intermedios. ^[2] La prueba del teorema de los cuatro colores es notable, además de su solución de un problema de un siglo de antigüedad, por ser la primera prueba importante asistida por computadora.

En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar el problema de coloración, que fue generalizado al polinomio de Tutte por WT Tutte , ambos invariantes importantes en la teoría de grafos algebraicos . Kempe ya había llamado la atención sobre el caso general no planar en 1879, ^[3] y muchos resultados sobre generalizaciones de la coloración de grafos planares 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 del grafo perfecto fuerte , motivada originalmente por un concepto de teoría de la información llamado capacidad de error cero de un grafo 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 grafos se ha estudiado como un problema algorítmico desde principios de los años 1970: el problema del número cromático (véase la sección § Coloración de vértices 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 en la recurrencia de eliminación-contracción de Zykov (1949). Una de las principales aplicaciones de la coloración de grafos, la asignación de registros en compiladores, se introdujo en 1981.

Cuando se utiliza sin ninguna calificación, la 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 de modo que ningún par de vértices que compartan la misma arista tenga el mismo color. Dado que un vértice con un bucle (es decir, una conexión directa con él mismo) nunca podría colorearse correctamente, se entiende que los gráficos en este contexto no tienen bucles.

La terminología del uso de colores para las etiquetas de vértices se remonta a la coloración de mapas. Las etiquetas como rojo y azul solo se utilizan cuando la cantidad de colores es pequeña 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 (propia) . El número más pequeño de colores necesarios para colorear un grafo G se denomina número cromático y, a menudo, se denota χ( G ) . A veces se utiliza γ( G ) , ya que χ( G ) también se utiliza para denotar la característica de Euler de un grafo. Un grafo al que se le puede asignar una k -coloración (propia) es k -coloreable 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 y 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 -coloreable tienen el mismo significado.

El polinomio cromático cuenta la cantidad de formas en que se puede colorear un gráfico utilizando algunos de un número dado de colores. Por ejemplo, utilizando tres colores, el gráfico en 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: utilizando 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 para cada elección de tres de los cuatro colores, hay 12 coloraciones de 3 colores válidas. Entonces, para el gráfico en el ejemplo, una tabla del número de coloraciones válidas 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 indica el nombre, para una G dada 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} .

Una coloración de aristas de un grafo es una coloración apropiada de las aristas , es decir, una asignación de colores a las aristas de modo que ningún vértice incida sobre dos aristas del mismo color. Una coloración de aristas con k colores se denomina k -coloración de aristas y es equivalente al problema de particionar el conjunto de aristas en k coincidencias . El menor número de colores necesarios para una coloración de aristas de un grafo G es el índice cromático , o número cromático de arista , χ ′( G ) . Una coloración de Tait es una coloración de 3 aristas de un grafo cúbico . El teorema de los cuatro colores es equivalente a la afirmación de que todo grafo cúbico plano sin puente admite una coloración de Tait.

La coloración total es un tipo de coloración de los vértices y aristas de un grafo. Cuando se utiliza 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, ninguna arista adyacente y ninguna arista y sus vértices finales. El número cromático total χ ″( G ) de un grafo G es la menor cantidad de colores necesarios en cualquier coloración total de G .

Para un gráfico con una fuerte incrustación en una superficie, la coloración de las caras es el dual del problema de coloración de los vértices.

Para un grafo G con una fuerte incrustación en una superficie orientable, William T. Tutte ^{[4] [5] [6]} descubrió que si el grafo es coloreable en k caras, entonces G admite un flujo k sin ningún punto de intersección . La equivalencia se cumple si la superficie es esférica.

Una coloración no etiquetada de un grafo es una órbita de una coloración bajo la acción del grupo de automorfismos del grafo. Los colores permanecen etiquetados; es el grafo el que queda sin etiquetar. Existe un análogo del polinomio cromático que cuenta el número de coloraciones no etiquetadas de un grafo a partir de un conjunto finito de colores dado.

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

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 . Un gráfico completo de n vértices requiere colores. En una coloración óptima debe haber al menos una de las m aristas 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á χ -limitada si existe alguna función tal que los gráficos en se pueden colorear con como máximo colores; para la familia de gráficos perfectos, esta función es .${\displaystyle {\mathcal {F}}}$${\displaystyle c}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle c(\omega (G))}$${\displaystyle c(\omega (G))=\omega (G)}$

Los grafos bicolores son exactamente los grafos bipartitos , incluidos los árboles y los bosques. Según el teorema de los cuatro colores, cada grafo plano puede tener cuatro colores.

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

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

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

Teorema de Brooks : para un grafo conexo y simple G , a menos que G sea un grafo completo o un ciclo impar.${\displaystyle \chi (G)\leq \Delta (G)}$

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 los gráficos perfectos, este límite es estricto. Encontrar camarillas se conoce como el problema de la camarilla .

Límite de Hoffman: Sea una matriz simétrica real tal que siempre que no sea una arista en . Defina , donde son los valores propios mayor y menor de . Defina , con como se indicó anteriormente. 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 quesiempre quesea una arista en. Definacomo el k mínimo para el queexiste 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 grafo complementario es también 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).}$

Los grafos con camarillas grandes tienen un número cromático alto, pero lo opuesto no es cierto. El grafo de Grötzsch es un ejemplo de un grafo 4-cromático sin triángulo, y el ejemplo se puede generalizar a los Mycielskianos .

Teorema ( William T. Tutte  1947, ^[8] Alexander Zykov 1949, Jan Mycielski  1955): Existen grafos libres de 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 inductivamente definida de grafos libres de triángulos pero con un número cromático arbitrariamente grande. ^[9] Burling (1965) construyó cajas alineadas con el eje en cuyo grafo de intersección está libre de triángulos y requiere arbitrariamente muchos colores para ser coloreados correctamente. Esta familia de grafos se llama entonces grafos de Burling. La misma clase de grafos se utiliza para la construcción de una familia de segmentos de línea libres de triángulos en el plano, dada por Pawlik et al. (2014). ^[10] Muestra que el número cromático de su grafo de intersección es arbitrariamente grande también. Por lo tanto, esto implica que las cajas alineadas con el eje en así como los segmentos de línea en no están χ -limitados . ^[10]${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}}$

Según el teorema de Brooks, los grafos con un número cromático alto deben tener un grado máximo alto. Pero la colorabilidad no es un fenómeno completamente local: un grafo con un perímetro alto se parece localmente a un árbol, porque todos los ciclos son largos, pero su número cromático no necesita ser 2:

Teorema ( Erdős ): Existen grafos con circunferencia y número cromático arbitrariamente altos. ^[11]

Una coloración de arista 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 todos los bordes 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 proporciona el teorema de Brooks para la coloración de vértices:

Teorema de Vizing: Un grafo de grado máximotiene número cromático de aristaso.${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta +1}$

Un grafo 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 de como máximo k ; este es el teorema de Gallai–Hasse–Roy–Vitaver (Nešetřil y Ossona de Mendez 2012).

Para los gráficos planares, las coloraciones de los vértices son esencialmente flujos duales a cero .

Se sabe mucho menos sobre los grafos infinitos. A continuación se presentan dos de los pocos resultados sobre la coloración de grafos infinitos:

• Si todos los subgrafos finitos de un grafo infinito G son k -coloreables, entonces también lo es G , bajo el supuesto del axioma de elección . Este es el teorema de 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).

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 distancia unitaria, es desconocido, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de grafos incluyen la conjetura de Hadwiger que establece que cada grafo 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 los grafos k -cromáticos los grafos completos son los que tienen el menor número de cruces .

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para los grafos planares G , el polinomio no tiene ceros en la región . Aunque se sabe que dicho polinomio cromático no tiene ceros en la región y que , su conjetura aún no se ha resuelto. También sigue siendo un problema sin resolver caracterizar los grafos 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}$

Coloración de gráficos
Decisión
Nombre	Coloración de gráficos, coloración de vértices, coloración k
Aporte	Grafo G con n vértices. Entero k
Producción	¿ G admite una coloración de vértices adecuada con k colores?
Duración del programa	O (2nn ) [ 12 ]
Complejidad	NP-completo
Reducción de	3-Satisfacción
Garey–Johnson	GT4
Mejoramiento
Nombre	Número cromático
Aporte	Grafo 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	Grafo G con n vértices. Entero k
Producción	El número P  ( G , k ) de coloraciones k propias de G
Duración del programa	O ( 2nn )​
Complejidad	♯P-completo
Aproximabilidad	FPRAS para casos restringidos
Inaproximabilidad	No se permite PTAS a menos que P = NP

Determinar si un gráfico se puede colorear con 2 colores es equivalente 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 una coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinomial mediante 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 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 se conoce su descomposición en ramas), se puede resolver en tiempo polinómico mediante 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 rama.

La búsqueda por fuerza bruta de una coloración k considera cada una de las asignaciones de k colores a n vértices y verifica si cada una es legal. Para calcular el número cromático y el polinomio cromático, se utiliza este procedimiento para cada , lo que no es 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 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 . ^[13] Utilizando el principio de inclusión-exclusión y el algoritmo de Yates para la transformación zeta rápida, la k -colorabilidad se puede decidir en el tiempo ^{[12] [14] [15] [16]} para cualquier k . Se conocen algoritmos más rápidos para 3- y 4-colorabilidad, que se pueden decidir en el tiempo ^[17] y ^[18] respectivamente. También se conocen algoritmos exponencialmente más rápidos para 5- y 6-colorabilidad, así como para familias restringidas de grafos , incluidos grafos dispersos. ^[19]${\displaystyle O(2.4423^{n})}$${\displaystyle O(2^{n}n)}$${\displaystyle O(1.3289^{n})}$${\displaystyle O(1.7272^{n})}$

La contracción de un grafo G es el grafo que se obtiene al identificar los vértices u y v y eliminar las aristas entre ellos. Las aristas restantes que originalmente eran incidentes a u o v ahora son incidentes a 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 grafos.${\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 grafo con la arista uv agregada. 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 grafo con la arista uv eliminada. representa el número de posibles coloraciones propias del grafo, donde los vértices pueden tener el mismo color o colores diferentes. Entonces las coloraciones propias surgen de dos grafos diferentes. Para explicarlo, si los vértices u y v tienen colores diferentes, entonces también podríamos considerar un grafo donde u y v son adyacentes. Si u y v tienen los mismos colores, también podríamos considerar un grafo donde u y v están contraídos. La curiosidad de Tutte sobre qué otras propiedades de grafos 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 grafos. 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 polinomial de para n vértices y m aristas. ^[20] El análisis se puede mejorar hasta dentro de un factor polinomial del número de árboles de expansión del grafo de entrada. ^[21] En la práctica, se emplean estrategias de ramificación y acotación y rechazo de isomorfismo de grafos para evitar algunas llamadas recursivas. El tiempo de ejecución depende de la heurística utilizada para elegir el par de vértices.${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$${\displaystyle t(G)}$

El algoritmo voraz considera los vértices en un orden específico , ..., y asigna al color más pequeño disponible no utilizado por los vecinos de 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 voraz con el número óptimo de colores. Por otro lado, las coloraciones voraces pueden ser arbitrariamente malas; 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 voraz 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}$

En el caso de los grafos cordales y de casos especiales de grafos cordales, como los grafos de intervalos y los grafos de indiferencia , se puede utilizar el algoritmo de coloración voraz para encontrar coloraciones óptimas en tiempo polinomial, eligiendo que el orden de los vértices sea el inverso de un orden de eliminación perfecto para el grafo. Los grafos perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estos grafos.

Si los vértices se ordenan según sus grados , la coloración voraz resultante utiliza como máximo colores, como máximo uno más que el grado máximo del grafo. Esta heurística a veces se denomina algoritmo de Welsh-Powell. ^[22] Otra heurística debida a Brélaz establece el ordenamiento de forma dinámica mientras el algoritmo avanza, eligiendo a continuación el vértice adyacente al mayor número de colores diferentes. ^[23] Muchas otras heurísticas de coloración de grafos se basan de forma similar en la coloración voraz 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 voraz, utilizando un orden de vértices elegido para maximizar este número, se denomina número de Grundy de un gráfico.

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

De manera similar al algoritmo de coloración voraz , 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 la mayor cantidad de colores diferentes en su entorno y colorea este vértice a continuación. Esto se define como el grado de saturación de un vértice determinado.

El algoritmo recursivo de primer orden de mayor tamaño funciona de una manera diferente: construye cada clase de color de a una por vez. Para ello, identifica un conjunto máximo independiente de vértices en el gráfico mediante reglas heurísticas especializadas. Luego, asigna a estos vértices el mismo color y los elimina del gráfico. Estas acciones se repiten en el subgráfico restante hasta que no queden vértices.

La complejidad del peor caso de DSatur es , donde es el número de vértices en el gráfico. El algoritmo también se puede implementar utilizando un montón binario para almacenar los grados de saturación, operando en donde es el número de aristas en el gráfico. ^[24] Esto produce ejecuciones mucho más rápidas con gráficos dispersos. La complejidad general de RLF es ligeramente superior a la de DSatur en . ^[24]${\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 , cíclicos y de rueda . ^[24]

Se sabe que un gráfico χ -cromático puede ser c -coloreado en el modelo LOCAL determinista, en . rondas, con . También se conoce un límite inferior coincidente de rondas. Este límite inferior se mantiene incluso si se permiten computadoras cuánticas que pueden intercambiar información cuántica, posiblemente con un estado entrelazado precompartido. ${\displaystyle O(n^{1/\alpha })}$${\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }$${\displaystyle \Omega (n^{1/\alpha })}$

En el campo de los algoritmos distribuidos , la coloración de grafos está estrechamente relacionada con el problema de la ruptura de la simetría . Los algoritmos aleatorios de última generación actuales 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. ^[25]

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 requieren. ^[25]

Una versión distribuida sencilla del algoritmo voraz para la coloración (Δ + 1) requiere Θ( n ) rondas de comunicación en el peor de los casos: puede ser necesario propagar la información de un lado de la red al otro.

El caso más simple e interesante es un ciclo n . Richard Cole y Uzi Vishkin ^[26] 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 una coloración triple de un ciclo n en O ( log * n ) pasos de comunicación (suponiendo 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 la 3-coloración de un n -ciclo. 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 grafos de grado acotado arbitrario; el tiempo de ejecución es poly(Δ) + O ( log *  n ). ^[27] La ​​técnica fue extendida a grafos de disco unitario por Schneider y Wattenhofer. ^[28] 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. ^[29] El algoritmo de Barenboim et al. se ejecuta en un 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 red 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 los bordes.

Los algoritmos descentralizados son aquellos en los que no se permite el paso de mensajes (en contraste con los algoritmos distribuidos en los que se produce 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 puede 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, suele ser 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 una coloración de gráfico adecuada con probabilidad uno. ^[30]

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

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. ^[34] Para todos los ε  > 0, aproximar el número cromático dentro de n ^{1− ε} es NP-hard . ^[35]

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

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

Para la coloración de los 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. ^[40] En términos de algoritmos de aproximación, el algoritmo de Vizing muestra que el número cromático del borde se puede aproximar a 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 de algoritmos de aproximación, aunque ninguno de los artículos hace uso explícito de esa noción. ^[41]

Modelos de coloración de vértices para una serie de problemas de programación . ^[42] En la forma más limpia, un conjunto dado de trabajos deben 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 pueden no asignarse 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 un borde para cada par de trabajos en conflicto. El número cromático del gráfico es exactamente el makespan mínimo , el tiempo óptimo para finalizar todos los trabajos sin conflictos.

Los detalles del problema de programación definen la estructura del gráfico. Por ejemplo, al asignar aeronaves a vuelos, el gráfico de conflictos resultante es un gráfico de intervalos , 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 conflictos resultante es un gráfico de disco unitario , por lo que el problema de coloración es 3-aproximable.

Un compilador es un programa informático que traduce un lenguaje de programación 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 rápidos del procesador . Lo ideal es que los valores se asignen a los registros de modo que todos puedan residir en ellos cuando se utilicen.

El enfoque de libro de texto para este problema es modelarlo como un problema de coloración de grafos. ^[43] El compilador construye un grafo de interferencia , donde los vértices son variables y una arista conecta dos vértices si se necesitan al mismo tiempo. Si el grafo se puede colorear con k colores, entonces cualquier conjunto de variables necesarias al mismo tiempo se puede almacenar en un máximo de k registros.

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

Una clase importante de problemas de coloración impropia se estudia en la teoría de Ramsey , donde las aristas del grafo se asignan a colores, y no hay restricción en los colores de las aristas incidentes. Un ejemplo simple es el teorema sobre amigos y extraños , que establece que en cualquier coloración de las aristas de , el grafo completo de seis vértices, habrá un triángulo monocromático; a menudo ilustrado diciendo que cualquier grupo de seis personas tiene tres extraños mutuos o tres conocidos mutuos. 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 dada.${\displaystyle K_{6}}$

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

• Gráfico crítico
• Juego de colorear gráficos
• Homomorfismo de grafos
• Construcción de Hajós
• Matemáticas del sudoku
• Gráfico multipartito
• Gráfico único en color

Wikimedia Commons tiene medios relacionados con Coloración de gráficos .

• Conjunto de algoritmos de coloración de gráficos de alto rendimiento de 8 algoritmos diferentes (implementados en C++) utilizados en el libro A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2015).
• Página para colorear gráficos de Joseph Culberson (programas para colorear gráficos)
• CoLoRaTiOn de Jim Andrews y Mike Fellows es un rompecabezas para colorear gráficos
• Enlaces a códigos fuente de Graph Coloring Archivado el 4 de julio de 2008 en Wayback Machine
• Código para calcular de manera eficiente los polinomios de 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 Jose Antonio Martin H.