Coloreado de gráficos

Cuando se utiliza sin ninguna especificación, la coloración de un grafo casi siempre se refiere a una coloración de vértices propiamente dicha , es decir, a la asignación de colores a los vértices del grafo de tal manera que no haya dos vértices que compartan la misma arista con el mismo color. Dado que un vértice con un bucle (es decir, una conexión directa consigo mismo) nunca podría colorearse correctamente, se entiende que los grafos en este contexto no tienen bucles.

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

Una coloración que utiliza como máximo k colores se denomina k -coloración (propia) . El número mínimo de colores necesarios para colorear un grafo G se denomina su número cromático y se suele denotar χ( G ) . ^{[ 5 ]} A veces se utiliza γ( G ) , ya que χ( G ) también se utiliza para denotar la característica de Euler de un grafo. ^{[ 6 ]} 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 ; 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 el número de maneras en que se puede colorear un grafo usando algunos de un número determinado de colores. Por ejemplo, usando tres colores, el grafo de la imagen adyacente se puede colorear de 12 maneras. Con solo 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 grafo de 4 vértices es una coloración propia); y para cada elección de tres de los cuatro colores, hay 12 coloraciones válidas de 3 colores. Entonces, para el grafo del 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 su nombre indica, para un G dado la función es efectivamente un polinomio en t . Para el gráfico de ejemplo, P ( G , t ) = t ( t − 1) ² ( t − 2) , y efectivamente 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 propia de las aristas , es decir, una asignación de colores a las aristas de tal manera que ningún vértice sea incidente a dos aristas del mismo color. Una coloración de aristas con k colores se denomina coloración de k aristas y es equivalente al problema de particionar el conjunto de aristas en k emparejamientos . El número mínimo de colores necesarios para una coloración de aristas de un grafo G es el índice cromático , o número cromático de aristas , χ ′ ( 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 planar sin puentes admite una coloración de Tait.

La coloración total es un tipo de coloración aplicada a los vértices y aristas de un grafo. Cuando se utiliza sin ninguna especificación, se asume que una coloración total es propia, en el sentido de que ningún vértice adyacente, ninguna arista adyacente, ni ninguna arista y sus vértices extremos tienen el mismo color. El número cromático total χ ″ ( G ) de un grafo G es el número mínimo de colores necesarios en cualquier coloración total de G.

Para un grafo con una fuerte incrustación en una superficie, la coloración de caras es el problema dual de la coloración de vértices.

Para un grafo G con una fuerte incrustación en una superficie orientable, William T. Tutte ^{[ 7 ] [ 8 ] [ 9 ]} descubrió que si el grafo es k -coloreable por caras, entonces G admite un k- flujo sin ceros en ningún lugar. La equivalencia se cumple si la superficie es una esfera.

Una coloración sin etiquetar 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 no tiene etiquetas. Existe un análogo del polinomio cromático que cuenta el número de coloraciones sin etiquetar 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 ser de un solo color son los gráficos sin aristas . Un gráfico completo${\displaystyle K_{n}}$de n vértices requiere${\displaystyle \chi (K_{n})=n}$colores. En una coloración óptima debe haber al menos una de las m aristas del grafo entre cada par de clases de color, por lo que

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

En términos más generales, una familia${\displaystyle {\mathcal {F}}}$de gráficos es χ -acotado si existe alguna función${\displaystyle c}$de tal manera que los gráficos${\displaystyle G}$en${\displaystyle {\mathcal {F}}}$puede colorearse con como máximo${\displaystyle c(\omega (G))}$colores, donde${\displaystyle \omega (G)}$es el número de camarilla de${\displaystyle G}$Para la familia de las gráficas perfectas, esta función es${\displaystyle c(\omega (G))=\omega (G)}$.

Los grafos 2-coloreables son precisamente los grafos bipartitos , incluyendo árboles y bosques. Según el teorema de los cuatro colores, todo grafo planar puede ser 4-coloreado.

Una coloración voraz muestra que cada grafo puede colorearse con un color más que el grado máximo del vértice ,

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

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

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

A lo largo de los años se han descubierto varios límites inferiores para el número cromático:

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 igual al número de la camarilla:

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

Para grafos perfectos, esta cota es ajustada. Encontrar camarillas se conoce como el problema de las camarillas .

El látigo de Hoffman: Déjalo${\displaystyle W}$sea ​​una matriz simétrica real tal que${\displaystyle W_{i,j}=0}$cuando sea${\displaystyle (i,j)}$no es una ventaja en${\displaystyle G}$. Definir${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$, dónde${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$son los valores propios más grandes y más pequeños de${\displaystyle W}$. Definir${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$, con${\displaystyle W}$como se indicó anteriormente. Luego:

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

Número cromático vectorial :Sea${\displaystyle W}$sea ​​una matriz semidefinida positiva tal que${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$cuando sea${\displaystyle (i,j)}$es una ventaja en${\displaystyle G}$. Definir${\displaystyle \chi _{V}(G)}$ser el menor k para el cual tal matriz${\displaystyle W}$existe. Entonces

${\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 una cota inferior del número cromático:

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

Número cromático fraccional : El número cromático fraccional de un grafo 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 grandes camarillas tienen un número cromático alto, pero lo contrario no es cierto. El grafo de Grötzsch es un ejemplo de un grafo 4-cromático sin triángulo, y este ejemplo se puede generalizar a los grafos de Mycielski .

Teorema ( WT Tutte , 1947 , ^{[ 11 ]} 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 dieron cada uno una construcción de una familia definida inductivamente de grafos libres de triángulos pero con un número cromático arbitrariamente grande. ^{[ 12 ]} Burling (1965) construyó cajas alineadas con ejes en${\displaystyle \mathbb {R} ^{3}}$cuyo grafo de intersección no contiene triángulos y requiere una cantidad arbitraria de colores para ser coloreado correctamente. Esta familia de grafos se denomina entonces grafos de Burling. La misma clase de grafos se utiliza para la construcción de una familia de segmentos de línea sin triángulos en el plano, dada por Pawlik et al. (2014). ^{[ 13 ]} Muestra que el número cromático de su grafo de intersección también es arbitrariamente grande. Por lo tanto, esto implica que las cajas alineadas con los ejes en${\displaystyle \mathbb {R} ^{3}}$así como segmentos de línea en${\displaystyle \mathbb {R} ^{2}}$no están acotados por χ . ^{[ 13 ]}

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 una circunferencia alta 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 grafos de circunferencia y número cromático arbitrariamente altos. ^{[ 14 ]}

Una coloración de aristas de G es una coloración de vértices de su grafo de líneas.${\displaystyle L(G)}$y viceversa. Por lo tanto,

${\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.${\displaystyle \Delta (G)}$. Dado que todas las aristas incidentes al mismo vértice necesitan su propio color, tenemos

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

Además,

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

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 gráfico de grado máximo${\displaystyle \Delta }$tiene número cromático de borde${\displaystyle \Delta }$o${\displaystyle \Delta +1}$.

Un grafo tiene una k -coloración 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 grafos planares, las coloraciones de vértices son esencialmente duales a los flujos sin cero en ninguna parte .

Se sabe mucho menos sobre 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 G también lo es , bajo la suposición del axioma de elección . Este es el teorema de De Bruijn-Erdős de De Bruijn y Erdős (1951) .
• Si un grafo admite una coloración completa de n elementos para cada n ≥ n ₀ , admite una coloración completa infinita ( Fawcett 1978 ) .

Como se indicó anteriormente,${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$Una conjetura de Reed de 1998 es que el valor está esencialmente más cerca del límite inferior,${\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, es desconocido, aunque es uno de 5, 6 o 7. Otros problemas abiertos relacionados con el número cromático de los grafos incluyen la conjetura de Hadwiger que afirma que todo 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 aquellos con 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 grafos planares${\displaystyle G}$, el polinomio${\displaystyle P(G,t)}$no tiene ceros en la región${\displaystyle [4,\infty )}$. Aunque se sabe que dicho polinomio cromático no tiene ceros en la región${\displaystyle [5,\infty )}$y eso${\displaystyle P(G,4)\neq 0}$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.

Determinar si un grafo puede colorearse con dos colores equivale a determinar si es bipartito o no , y por lo tanto, computable en tiempo lineal mediante búsqueda en amplitud o en profundidad . De forma más general, el número cromático y una coloración correspondiente de grafos perfectos pueden calcularse en tiempo polinomial mediante programación semidefinida . Se conocen fórmulas cerradas para polinomios cromáticos en muchas clases de grafos, como bosques, grafos cordales, ciclos, ruedas y escaleras, por lo que pueden evaluarse en tiempo polinomial.

Si el grafo es planar y tiene pocas ramas (o no planar pero con una descomposición en ramas conocida ), se puede resolver en tiempo polinomial mediante programación dinámica. En general, el tiempo requerido es polinomial con respecto al tamaño del grafo, pero exponencial con respecto a la anchura de las ramas.

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

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 tiempo y espacio.${\displaystyle O(2.4423^{n})}$. ^{[ 16 ]} 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${\displaystyle O(2^{n}n)}$^{[ 15 ] [ 17 ] [ 18 ] [ 19 ]} para cualquierk. Se conocen algoritmos más rápidos para la 3- y 4-colorabilidad, que se pueden decidir en el tiempo${\displaystyle O(1.3289^{n})}$^{[ 20 ]} y${\displaystyle O(1.7272^{n})}$, ^{[ 21 ]} respectivamente. También se conocen algoritmos exponencialmente más rápidos para la 5- y 6-colorabilidad, así como para familias restringidas de grafos, incluidos los grafos dispersos. ^{[ 22 ]}

La contracción${\displaystyle G/uv}$La coloración de un grafo G se obtiene al identificar los vértices u y v , y eliminar las aristas entre ellos. Las aristas restantes, originalmente incidentes a u o v, ahora son incidentes a su nodo identificado ( es decir , al nuevo nodo fusionado uv ). Esta operación desempeña un papel fundamental en el análisis de la coloración de grafos.

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${\displaystyle G+uv}$es el grafo con la arista uv añadida. 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 .

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${\displaystyle G-uv}$es el gráfico con el uv del borde eliminado.${\displaystyle P(G-uv,k)}$representa el número de posibles coloraciones propias del grafo, donde los vértices pueden tener el mismo o diferente color. Entonces, las coloraciones propias surgen de dos grafos diferentes. Para explicarlo, si los vértices u y v tienen colores diferentes, entonces podríamos considerar un grafo donde u y v son adyacentes. Si u y v tienen el mismo color, podríamos considerar un grafo donde u y v son contraídos. La curiosidad de Tutte sobre qué otras propiedades de los grafos 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 constituye la base de muchos algoritmos para la coloración de 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 un tiempo con un factor polinomial de${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$para n vértices y m aristas. ^{[ 23 ]} El análisis se puede mejorar hasta un factor polinomial del número${\displaystyle t(G)}$de árboles de expansión del grafo de entrada. ^{[ 24 ]} 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 seleccionar el par de vértices.

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

Para grafos cordales , y para casos especiales de grafos cordales como los grafos de intervalos y los grafos de indiferencia , el algoritmo de coloración voraz puede utilizarse 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 el grafo. Los grafos perfectamente ordenables generalizan esta propiedad, pero encontrar un orden perfecto para estos grafos es un problema NP-difícil.

Si los vértices se ordenan según sus grados , el coloreado voraz resultante utiliza como máximo${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$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. ^{[ 25 ]} 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. ^{[ 26 ]} Muchas otras heurísticas de coloración de grafos se basan de manera similar en la coloración voraz para una estrategia específica estática o dinámica de ordenamiento de los vértices; estos algoritmos a veces se denominan algoritmos de coloración secuencial .

El número máximo (peor) de colores que puede obtener el algoritmo voraz, utilizando un ordenamiento de vértices elegido para maximizar este número, se denomina número de Grundy de un grafo.

Dos heurísticas bien conocidas de tiempo polinomial para la coloración de grafos son los algoritmos DSatur y de búsqueda recursiva del mayor primero (RLF).

De forma similar al algoritmo de coloración voraz , DSatur colorea los vértices de un grafo uno tras otro, utilizando un color previamente no usado cuando sea 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 vecindario y lo colorea a continuación. Esto se define como el grado de saturación de un vértice dado.

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

La complejidad en el peor de los casos de DSatur es${\displaystyle O(n^{2})}$, dónde${\displaystyle n}$es el número de vértices en el grafo. El algoritmo también se puede implementar utilizando un montón binario para almacenar grados de saturación, operando en${\displaystyle O((n+m)\log n)}$dónde${\displaystyle m}$es el número de aristas en el grafo. ^{[ 27 ]} Esto produce ejecuciones mucho más rápidas con grafos dispersos. La complejidad general de RLF es ligeramente superior a la de DSatur en${\displaystyle O(mn)}$. ^{[ 27 ]}

DSatur y RLF son exactos para grafos bipartitos , cíclicos y de rueda . ^{[ 27 ]}

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

En el campo de los algoritmos distribuidos , la coloración de grafos está estrechamente relacionada con el problema de la ruptura de simetría . Los algoritmos aleatorios más avanzados actualmente son más rápidos que los algoritmos deterministas para un grado máximo Δ suficientemente grande. Los algoritmos aleatorios más rápidos emplean la técnica de ensayos múltiples de Schneider y Wattenhofer. ^{[ 28 ]}

En un grafo simétrico , un algoritmo distribuido determinista no puede encontrar una coloración de vértices adecuada. Se necesita 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, asumimos que se nos proporciona una coloración de n colores. El desafío consiste en 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. ^{[ 28 ]}

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; es posible que sea necesario propagar información de un lado de la red a otro.

El caso interesante más sencillo es un ciclo de n colores . Richard Cole y Uzi Vishkin ^{[ 29 ]} demuestran que existe un algoritmo distribuido que reduce el número de colores de n a O (log n ) en un paso de comunicación síncrona. Al iterar el mismo procedimiento, es posible obtener una coloración de 3 colores de un ciclo de n colores 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 de tiempo constante para 3-colorear un n -ciclo. Linial (1992) demostró que esto no es posible: cualquier algoritmo distribuido determinista requiere Ω( log * n ) pasos de comunicación para reducir un n -coloreado a un 3-coloreado 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 ). ^{[ 30 ]} La técnica fue extendida a grafos de disco unitario por Schneider y Wattenhofer. ^{[ 31 ]} Los algoritmos deterministas más rápidos para la coloración (Δ + 1) para Δ pequeño se deben a Leonid Barenboim, Michael Elkin y Fabian Kuhn. ^{[ 32 ]} El algoritmo de Barenboim et al. se ejecuta en 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 a la cota inferior de Linial. Panconesi y Srinivasan (1996) utilizan descomposiciones de red para calcular una coloración Δ+1 en tiempo     ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$.

El problema de la coloración de aristas también se ha estudiado en el modelo distribuido. Panconesi y Rizzi (2001) lograron una coloración (2Δ − 1) en tiempo O (Δ + log * n ) en este modelo. La cota inferior para la coloración de vértices distribuida, debida a Linial (1992), también se aplica al problema de la coloración de aristas distribuida.     

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 local), y existen algoritmos descentralizados eficientes que colorean un grafo si existe una coloración adecuada. Estos algoritmos asumen que un vértice puede detectar si alguno de sus vecinos está utilizando el mismo color que él, es decir, si existe un conflicto local. Esta es una suposición razonable 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 interferentes están utilizando el mismo canal (por ejemplo, midiendo la relación señal/ruido más interferencia). Esta información de detección es suficiente para que los algoritmos basados ​​en autómatas de aprendizaje encuentren una coloración adecuada del grafo con probabilidad uno. ^{[ 33 ]}

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-difícil calcular el número cromático. ^{[ 34 ]} El problema de la 3-coloración sigue siendo NP-completo incluso en grafos planares 4-regulares . ^{[ 35 ]} Sin embargo, en grafos con grado máximo 3 o menor, el teorema de Brooks implica que el problema de la 3-coloración puede resolverse 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. ^{[ 36 ]}

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

También es NP-difícil colorear un grafo 3-coloreable con 5 colores, ^{[ 39 ]} un grafo 4-coloreable con 7 colores, ^{[ 39 ]} y un grafo k -coloreable con${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$colores para k ≥ 5. ^{[ 40 ]}

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

Para la coloración de bordes, la demostración 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. ^{[ 43 ]} 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 dificultad muestra que no existe ningún algoritmo (4/3 − ε ) para ningún ε > 0 a menos que P = NP . Estos son algunos de los resultados más antiguos en la literatura de algoritmos de aproximación, aunque ninguno de los artículos hace un uso explícito de esa noción. ^{[ 44 ]}    

Modelos de coloración de vértices para varios problemas de programación . ^{[ 45 ]} En su forma más limpia, un conjunto dado de trabajos debe asignarse a intervalos de tiempo, y cada trabajo requiere un intervalo de tiempo. Los trabajos pueden programarse en cualquier orden, pero pares de trabajos pueden estar en conflicto en el sentido de que no pueden asignarse al mismo intervalo de tiempo, por ejemplo, porque ambos dependen de un recurso compartido. El grafo correspondiente contiene un vértice por cada trabajo y una arista por cada par de trabajos en conflicto. El número cromático del grafo es exactamente el tiempo de finalización mínimo , el tiempo óptimo para terminar todos los trabajos sin conflictos.

Los detalles del problema de programación definen la estructura del grafo. Por ejemplo, al asignar aeronaves a vuelos, el grafo de conflictos resultante es un grafo 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 grafo de conflictos resultante es un grafo 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 almacenan en los registros rápidos del procesador . Idealmente, los valores se asignan a los registros de forma que puedan residir en ellos cuando se utilicen.

El enfoque estándar para este problema consiste en modelarlo como un problema de coloración de grafos. ^{[ 46 ]} El compilador construye un grafo de interferencia , donde los vértices son variables y una arista conecta dos vértices si se necesitan simultáneamente. Si el grafo se puede colorear con k colores, 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 deportiva, ^{[ 47 ]} el diseño de planos de asientos, ^{[ 48 ]} la elaboración de horarios de exámenes, ^{[ 49 ]} la programación de taxis, ^{[ 50 ]} y la resolución de rompecabezas de Sudoku . ^{[ 51 ]}

Una clase importante de problemas de coloración impropia se estudia en la teoría de Ramsey , donde a las aristas del grafo se les asignan 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${\displaystyle K_{6}}$En el grafo completo de seis vértices, habrá un triángulo monocromático; esto se suele ilustrar diciendo que cualquier grupo de seis personas tiene tres desconocidos entre sí o tres conocidos en común. La teoría de Ramsey se ocupa de generalizar esta idea para buscar regularidad en medio del desorden, encontrando condiciones generales para la existencia de subgrafos monocromáticos con una estructura dada.

La coloración modular es un tipo de coloración de grafos en la que el color de cada vértice es la suma de los colores de sus vértices adyacentes.

Dejar${\displaystyle k\geq 2}$ser una serie de colores donde${\displaystyle \mathbb {Z} _{k}}$es el conjunto de enteros módulo${\displaystyle k}$compuesto por los elementos (o colores)${\displaystyle 0,1,2,...,k-2,k-1}$. Primero, coloreamos cada vértice en${\displaystyle G}$utilizando los elementos de${\displaystyle \mathbb {Z} _{k}}$, permitiendo que a dos vértices adyacentes se les asigne el mismo color. En otras palabras, queremos${\displaystyle c}$ser un color tal que${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$donde a los vértices adyacentes se les puede asignar el mismo color.

Para cada vértice${\displaystyle v}$en${\displaystyle G}$, la suma de colores de${\displaystyle v}$,${\displaystyle \sigma (v)}$, es la suma de todos los vértices adyacentes a${\displaystyle v}$módulo${\displaystyle k}$. La suma de colores de${\displaystyle v}$se denota por

${\displaystyle \sigma (v)=\sum _{u\in N(v)}c(u),}$

dónde${\displaystyle u}$es un vértice arbitrario en la vecindad de${\displaystyle v}$,${\displaystyle N(v)}$Luego, coloreamos cada vértice con el nuevo color determinado por la suma de los vértices adyacentes. El gráfico${\displaystyle G}$tiene un diseño modular${\displaystyle k}$-coloración si, para cada par de vértices adyacentes${\displaystyle a}$y${\displaystyle b}$,${\displaystyle \sigma (a)\neq \sigma (b)}$. El número cromático modular de${\displaystyle G}$,${\displaystyle mc(G)}$, es el valor mínimo de${\displaystyle k}$de tal manera que exista un modular${\displaystyle k}$-coloración de${\displaystyle G}$.

Por ejemplo, supongamos que hay un vértice${\displaystyle v}$adyacentes a los vértices con los colores asignados${\displaystyle 0,1,1}$, y${\displaystyle 3{\bmod {4}}}$(eso es,${\displaystyle k=4}$). La suma de colores sería${\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}}$Este sería el nuevo color del vértice.${\displaystyle v}$Repetiríamos este proceso para cada vértice en${\displaystyle G}$. Si ninguno de los vértices adyacentes tiene sumas de color iguales,${\displaystyle G}$tiene un módulo${\displaystyle 4}$colorante.

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