Coloración de gráficos (Graph coloring)

En teoría de grafos, colorear gráficos implica la asignación sistemática de etiquetas, convencionalmente denominadas "colores", a elementos dentro de un gráfico. Esta asignación se rige por restricciones específicas, que normalmente prohíben que elementos adyacentes compartan el mismo color. Este concepto representa una instancia especializada de etiquetado de gráficos. La aplicación más fundamental consiste en asignar colores a los vértices de un gráfico de modo que no haya dos vértices adyacentes que posean colores idénticos; esta técnica específica se conoce como coloración de vértices. En consecuencia, una coloración de bordes implica asignar un color a cada borde, asegurando que no haya dos bordes incidentes que compartan el mismo color. Además, para los gráficos planos, una coloración de caras implica asignar un color a cada cara (o región) de manera que no se asigne el mismo color a dos caras que comparten un límite común.

La coloración de vértices con frecuencia sirve como concepto introductorio para los problemas de coloración de gráficos, dado que otros desafíos de coloración se pueden reformular como ejemplos de coloración de vértices. Por ejemplo, la coloración de los bordes de un gráfico es equivalente a la coloración de los vértices de su gráfico lineal, y la coloración de las caras de un gráfico plano corresponde a la coloración de los vértices de su gráfico dual. Sin embargo, los problemas que no involucran directamente la coloración de vértices a menudo se presentan y analizan en sus formas originales. Este enfoque se debe en parte a consideraciones pedagógicas y en parte a que ciertos problemas, como la coloración de los bordes, se investigan más eficazmente en sus formulaciones sin vértices.

La práctica de emplear "colores" en este contexto surge de la tarea histórica de colorear países en mapas políticos, donde cada región estaba físicamente coloreada. Posteriormente, este concepto se amplió a la coloración de caras dentro de un gráfico incrustado en un plano. A través del principio de dualidad plana, esto evolucionó hacia la coloración de vértices, una forma que se generaliza en todo tipo de gráficos. Dentro de los marcos matemáticos y computacionales, es habitual representar estos "colores" utilizando la secuencia inicial de números enteros positivos o no negativos. En términos más generales, cualquier conjunto finito puede servir como "conjunto de colores" designado. Las características fundamentales de un problema de coloración están determinadas por la cantidad de colores disponibles, más que por sus identidades específicas.

La coloración de gráficos presenta numerosas aplicaciones prácticas junto con importantes desafíos teóricos. Más allá de los tipos de problemas convencionales, se pueden imponer varias restricciones a la estructura del gráfico, la metodología de asignación o incluso las propiedades de los colores mismos. Los principios subyacentes incluso han ganado reconocimiento público a través del popular rompecabezas numérico Sudoku. En consecuencia, la coloración de gráficos sigue siendo un área muy dinámica de investigación en curso.

Antecedentes históricos

Historial

Las primeras investigaciones sobre la coloración de gráficos se centraron predominantemente en gráficos planos, específicamente en el contexto de la coloración de mapas. En 1852, mientras intentaba colorear un mapa de los condados ingleses, Francis Guthrie propuso la conjetura de los cuatro colores, observando que cuatro colores parecían adecuados para colorear cualquier mapa de modo que ninguna región adyacente compartiera un color idéntico. Frederick Guthrie, hermano de Francis, posteriormente transmitió este problema a su profesor de matemáticas, Augustus De Morgan del University College, quien luego hizo referencia a él en correspondencia con William Hamilton durante el mismo año. Arthur Cayley presentó formalmente el problema en una reunión de la Sociedad Matemática de Londres en 1879. Ese mismo año, Alfred Kempe publicó un artículo afirmando una solución, lo que llevó a que el problema de los cuatro colores se considerara resuelto durante aproximadamente una década. En reconocimiento a este logro, Kempe fue elegido miembro de la Royal Society y más tarde sirvió como presidente de la London Mathematical Society.

En 1890, Percy John Heawood demostró el defecto del argumento de Kempe. Sin embargo, en la misma publicación, Heawood demostró el teorema de los cinco colores, estableciendo que cualquier mapa plano se puede colorear usando un máximo de cinco colores, basándose en los conceptos fundamentales de Kempe. Durante el siglo siguiente, extensas investigaciones y avances teóricos tuvieron como objetivo reducir el número requerido de colores a cuatro, culminando en la demostración definitiva del teorema de los cuatro colores en 1976 por Kenneth Appel y Wolfgang Haken. En particular, su demostración revisó las ideas originales de Heawood y Kempe, evitando en gran medida desarrollos teóricos intermedios. Más allá de resolver un desafío matemático centenario, la demostración del teorema de los cuatro colores es importante como la primera prueba importante asistida por computadora en matemáticas.

En 1912, George David Birkhoff introdujo el polinomio cromático como una herramienta para analizar problemas de coloración; Este concepto fue posteriormente generalizado por W. T. Tutte en el polinomio de Tutte. Ambos polinomios son reconocidos como invariantes cruciales dentro de la teoría de grafos algebraicos. Kempe había destacado previamente los escenarios más amplios y no planos en 1879, lo que llevó a numerosos hallazgos posteriores a principios del siglo XX sobre la generalización de la coloración de gráficos planos a superficies de género topológico superior.

En 1960, Claude Berge propuso otra conjetura sobre la coloración de gráficos, denominada conjetura fuerte del gráfico perfecto. Esta propuesta se inspiró inicialmente en el concepto teórico de la información de Shannon de capacidad de error cero en gráficos. La conjetura permaneció sin demostrarse durante 40 años hasta 2002, cuando Chudnovsky, Robertson, Seymour y Thomas la establecieron de manera concluyente como el célebre teorema del gráfico perfecto fuerte.

La coloración de gráficos se ha investigado como un problema algorítmico desde principios de los años 1970. El problema de los números cromáticos, identificado en 1972, es uno de los 21 problemas NP-completos de Karp. Alrededor del mismo período, se idearon varios algoritmos de tiempo exponencial, empleando técnicas como el retroceso y la recurrencia de eliminación-contracción de Zykov en 1949. En 1981 se introdujo una aplicación principal de coloración de gráficos, la asignación de registros en compiladores.

Definiciones y terminología

Colorear vértice

Cuando se utiliza sin más calificaciones, una coloración de gráfico casi invariablemente significa una coloración de vértice adecuada. Este proceso implica asignar etiquetas distintas, o 'colores', a los vértices de un gráfico de modo que no haya dos vértices conectados por un borde que compartan el mismo color. En consecuencia, se entiende que los gráficos considerados en este contexto no tienen bucles, ya que un vértice con un bucle (una conexión directa consigo mismo) no se puede colorear adecuadamente.

La convención de usar colores para las etiquetas de los vértices tiene sus orígenes en la coloración del mapa. Las designaciones de colores específicos, como rojo y azul, generalmente se emplean sólo cuando el número total de colores es pequeño. En la mayoría de los contextos, se entiende que estas etiquetas se extraen del conjunto de números enteros positivos, {1, 2, 3,...}.

Una coloración que emplea como máximo k colores se denomina coloración (adecuada) k. El número mínimo de colores necesarios para colorear correctamente un gráfico G se define como su número cromático, comúnmente indicado por χ(G). La notación γ(G) a veces se usa indistintamente, ya que χ(G) también representa la característica de Euler de un gráfico. Un gráfico al que se le puede asignar una coloración k (adecuada) se denomina k-colorable y se designa k-cromático si su número cromático es exactamente k. Un subconjunto de vértices que comparten el mismo color se conoce como clase de color; cada una de estas clases forma inherentemente un conjunto independiente. Por lo tanto, una coloración k es equivalente a una partición del conjunto de vértices en k conjuntos independientes, lo que convierte los términos k-partite y k-colorable en sinónimos.

Polinomio cromático

El polinomio cromático enumera las distintas formas en que se puede colorear un gráfico utilizando un número específico de colores disponibles. Por ejemplo, un gráfico ilustrativo se puede colorear de 12 maneras cuando se utilizan tres colores. Por el contrario, con sólo dos colores no se puede conseguir ninguna coloración válida. Si hay cuatro colores disponibles, el gráfico se puede colorear de 24 + 4 × 12 = 72 formas. ¡Este total representa 4! = 24 coloraciones válidas cuando se emplean los cuatro colores (ya que cada asignación de cuatro colores a cualquier gráfico de 4 vértices constituye una coloración adecuada), además de 12 3 coloraciones válidas para cada selección de tres colores de los cuatro disponibles. Así, para el gráfico de ejemplo, una tabla que detalle el número de colorantes válidos comenzaría de la siguiente manera:

El polinomio cromático está representado por la función P(G, t), que cuantifica el número de t-coloraciones para un gráfico G. Como sugiere su nombre, para cualquier gráfico G, esta función es de hecho un polinomio en la variable t. Para el gráfico de ejemplo, el polinomio cromático es P(G, t) = t(t − 1)§2728§(t − 2), y se confirma que P(G, 4) = 72.

El polinomio cromático ofrece una visión más completa de la colorabilidad del gráfico G que el número cromático solo. Específicamente, χ se define como el entero positivo más pequeño que no es una raíz (cero) del polinomio cromático, expresado formalmente como χ(G) = min{k : P(G, k) > 0}.

Coloreado de bordes

Una coloración de bordes de un gráfico se define como una coloración adecuada de sus bordes, lo que implica asignar colores a los bordes de manera que no se asigne el mismo color a dos bordes que comparten un vértice común. Una coloración de borde que utiliza k colores se denomina k-coloración de borde y corresponde a la tarea de dividir el conjunto de bordes del gráfico en k coincidencias distintas. El número mínimo de colores requeridos para colorear los bordes de un gráfico G se designa como su índice cromático, también conocido como número cromático de bordes, denotado por χ′(G). Una coloración Tait se refiere específicamente a una coloración de 3 aristas de un gráfico cúbico. El teorema de los cuatro colores se puede expresar de manera equivalente como la proposición de que todas las gráficas planas, cúbicas y sin puentes poseen una coloración Tait.

Coloración total

coloración total implica asignar colores a los vértices y de un gráfico. Por convención, una coloración total no calificada se considera adecuada, lo que implica que ningún vértice adyacente, ni aristas adyacentes, ni ninguna arista y sus vértices incidentes comparten el mismo color. El número cromático total, denotado χ″(G), para un gráfico G representa el número mínimo de colores requeridos para cualquier coloración total de G.

Coloración de cara

En el contexto de un gráfico fuertemente incrustado en una superficie, la coloración de caras constituye el doble problema de la coloración de vértices.

Teoría del flujo de Tutte

Para un gráfico G con una fuerte incrustación en una superficie orientable, William T. Tutte demostró que si un gráfico es k-face-colorable, entonces G posee un flujo k de cero en ninguna parte. Esta equivalencia es válida cuando la superficie en cuestión es una esfera.

Colorear sin etiqueta

Una coloración sin etiqueta de un gráfico se define como una órbita de una coloración bajo la influencia del grupo de automorfismos del gráfico. Si bien los colores conservan sus etiquetas, el gráfico en sí se considera sin etiquetas en este contexto. Existe un concepto análogo al polinomio cromático, que enumera los colores sin etiquetar de un gráfico utilizando un conjunto finito específico de colores.

Cuando el color de un gráfico en d vértices se conceptualiza como un vector dentro de ⁠${\displaystyle \mathbb {Z} ^{d}}$⁠, la operación de un automorfismo corresponde a una permutación de los coeficientes dentro de este vector colorante.

Propiedades

Límites superiores del número cromático

Asignar colores distintos a vértices distintos da como resultado consistentemente una coloración adecuada; en consecuencia,

§67§ ≤ χ ( G ) ≤ n . {\displaystyle 1\leq \chi (G)\leq n.}

Solo los gráficos sin bordes se pueden colorear con 1 color. Un gráfico completo, denotado K n {\displaystyle K_n}, que comprende n vértices, requiere ${\displaystyle \chi (K_{n})=n}$ colores. Dentro de una coloración óptima, al menos uno de los bordes m del gráfico debe conectar cada par de clases de colores distintas; por lo tanto,

χ<!-- χ --> ( G ) ( χ<!-- χ --> ( G ) −<!-- − --> §2930§ ) ≤ §3637§ m . {\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}

En términos más generales, una familia ${\displaystyle {\mathcal {F}}}$ de gráficos χ-limitado si una función ${\displaystyle c}$ existe de modo que cualquier gráfico ${\displaystyle G}$ dentro de ${\displaystyle {\mathcal {F}}}$ se puede colorear usando como máximo ${\displaystyle c(\omega (G))}$ colores. Aquí, ${\displaystyle \omega (G)}$ denota el número de camarilla de ${\displaystyle G}$. Para la familia específica de gráficos perfectos, esta función se define como ${\displaystyle c(\omega (G))=\omega (G)}$.

Los gráficos con dos colores son precisamente los gráficos bipartitos, una categoría que abarca árboles y bosques. Según el teorema de los cuatro colores, cualquier gráfico plano se puede colorear con un máximo de cuatro colores.

El uso de un algoritmo de coloración voraz demuestra que cualquier gráfico se puede colorear usando un número de colores igual a uno más que su grado máximo de vértice.

Esta relación se expresa formalmente como ${\displaystyle \chi (G)\leq \Delta (G)+1.}$.

Para gráficos completos, el número cromático es ${\displaystyle \chi (G)=n}$ y el grado máximo es Δ<!-- Δ -->(G)=n−<!-- − -->§4950§{\displaystyle \Delta (G)=n-1}. De manera similar, los ciclos impares exhiben ${\displaystyle \chi (G)=3}$ y Δ<!-- Δ -->(G)=§103104§{\displaystyle \Delta (G)=2}. En consecuencia, para estos tipos de gráficos específicos, el límite antes mencionado es óptimo. Sin embargo, en todos los demás escenarios, este límite se puede mejorar marginalmente, como lo expresa el teorema de Brooks, que establece que:

teorema de Brooks afirma que ${\displaystyle \chi (G)\leq \Delta (G)}$ para cualquier gráfico simple y conectado G, con la excepción de gráficos completos y ciclos impares.

Límites inferiores para el número cromático

Con el tiempo, se han establecido varios límites inferiores para el número cromático:

Si un gráfico G posee un grupo de tamaño k, se requerirá un mínimo de k colores para colorear ese grupo específico. Esto implica que el número cromático debe ser al menos equivalente al número de camarilla:

El número cromático de un gráfico G, denotado χ(G), siempre es mayor o igual a su número de camarilla, ω(G), como lo expresa la desigualdad {\displaystyle \chi (G)\geq \omega (G).}

Para gráficos perfectos, este límite se cumple con precisión. La tarea computacional de identificar camarillas se conoce como problema de camarillas.

Límite de Hoffman: Considere ${\displaystyle W}$ como una matriz simétrica real donde sus elementos Wi,j=§3839§{\displaystyle W_{i,j}=0} si el par ${\displaystyle (i,j)}$ no constituye una arista en el gráfico ${\displaystyle G}$. Definimos ${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$, donde ${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$ representan los valores propios máximo y mínimo de ${\displaystyle W}$.Posteriormente, ${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$ se define como el valor máximo de χW(G) sobre todas estas matrices ${\displaystyle W}$. Esto lleva a la siguiente relación:

La desigualdad resultante establece que χH(G) es menor o igual a χ(G), expresado formalmente como {\displaystyle \chi _{H}(G)\leq \chi (G).}

Número cromático vectorial: Considere una matriz semidefinida positiva ${\displaystyle W}$ tal que para cada borde ${\displaystyle (i,j)}$ dentro de un gráfico ${\displaystyle G}$, la desigualdad Wi,j≤<!-- ≤ -->−<!-- − -->§5152§k−§5960§{\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}} mantiene. El ${\displaystyle \chi _{V}(G)}$ es definido como el entero más pequeño k para el cual dicha matriz ${\displaystyle W}$ existe.

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

Número de Lovász: El número de Lovász de un grafo complementario también establece un límite inferior para el número cromático.

Esta relación se expresa como: ${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

Número cromático fraccionario: el número cromático fraccionario de un gráfico también proporciona un límite inferior para su número cromático.

Esto está representado por la desigualdad: ${\displaystyle \chi _{f}(G)\leq \chi (G).}$

Los límites antes mencionados se ordenan jerárquicamente de la siguiente manera:

El orden completo viene dado por: ${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

Gráficos caracterizados por números cromáticos elevados

Los gráficos que poseen camarillas grandes invariablemente exhiben un número cromático alto; sin embargo, lo contrario no se cumple. El gráfico de Grötzsch ejemplifica esto, siendo un gráfico cuatricromático sin triángulos, característica que puede extenderse mediante la construcción de los mycielskianos.

Teorema (W. T. Tutte, 1947; Alexander Zykov, 1949; Jan Mycielski, 1955): Los gráficos sin triángulos pueden poseer un número cromático arbitrariamente alto.

Para fundamentar este teorema, Mycielski y Zykov desarrollaron de forma independiente construcciones inductivas para familias de gráficos sin triángulos que exhiben números cromáticos arbitrariamente grandes. Posteriormente, Burling (1965) demostró este fenómeno construyendo cajas alineadas con ejes en ${\displaystyle \mathbb {R} ^{3}}$ cuyo gráfico de intersección no tiene triángulos y requiere una cantidad arbitraria de colores para una coloración adecuada. Esta familia específica de gráficos se conoce como gráficos de Burling. Además, Pawlik et al. (2014) utilizaron esta misma clase de gráficos para construir una familia de segmentos de línea sin triángulos dentro del plano, revelando que el número cromático de su gráfico de intersección también es arbitrariamente grande. En consecuencia, esto implica que ambos cuadros alineados con los ejes en ${\displaystyle \mathbb {R} ^{3}}$ y segmentos de línea en ${\displaystyle \mathbb {R} ^{2}}$ no están acotados por χ.

Según el teorema de Brooks, los gráficos caracterizados por un número cromático alto también deben poseer un grado máximo alto. Sin embargo, la colorabilidad no es una propiedad exclusivamente local. Por ejemplo, un gráfico con una circunferencia alta se parece localmente a un árbol debido a sus ciclos extendidos, pero su número cromático no es necesariamente 2.

Teorema (Erdős): Pueden existir gráficas con circunferencia y número cromático arbitrariamente altos.

Límites del índice cromático

La coloración de los bordes de un gráfico G es equivalente a la coloración de los vértices de su gráfico lineal L ( G ) {\displaystyle L(G)} y viceversa. En consecuencia,

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

Existe una correlación significativa entre la colorabilidad de los bordes y el grado máximo de un gráfico, indicado como Δ<!-- Δ --> ( G ) {\displaystyle \Delta (G)}. Dado que a todas las aristas incidentes en un vértice común se les deben asignar colores distintos, se deduce que:

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

Además,

teorema de Kőnig establece que ${\displaystyle \chi '(G)=\Delta (G)}$ si el gráfico G es bipartito.

Generalmente, esta relación es incluso más sólida que la establecida por el teorema de Brooks para la coloración de los vértices.

Teorema de Vizing: El teorema de Vizing establece que cualquier gráfica con un grado máximo de ${\displaystyle \Delta }$ posee un número cromático de borde igual a ${\displaystyle \Delta }$ o ${\displaystyle \Delta +1}$.

Propiedades adicionales

Un gráfico es k-colorable si y sólo si admite una orientación acíclica donde la longitud máxima del camino no excede k; este principio se conoce como teorema de Gallai-Hasse-Roy-Vitaver (Nešetřil & Ossona de Mendez 2012).

En el contexto de los gráficos planos, la coloración de los vértices exhibe una dualidad fundamental con flujos en ninguna parte cero.

El conocimiento sobre los gráficos infinitos es considerablemente más limitado. Las declaraciones siguientes representan dos de los escasos hallazgos relacionados con la coloración de gráficos infinitos:

• Asumiendo el axioma de elección, si cada subgrafo finito de un gráfico infinito G es k-colorable, entonces el gráfico G en sí también es k-colorable. Este principio se formaliza como el teorema de de Bruijn-Erdős (de Bruijn & Erdős 1951).
• Un gráfico que permite una coloración n completa para todos los valores n mayores o iguales a n§67§ también posee una coloración completa infinita (Fawcett 1978).

Problemas no resueltos

Como se estableció anteriormente, la desigualdad ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$ se mantiene. Una conjetura propuesta por Reed en 1998 postula que el número cromático está fundamentalmente más cerca del límite inferior, específicamente χ<!-- χ -->(G)≤<!-- ≤ -->⌈ω<!-- ω -->(G)+Δ<!-- Δ -->(G)+§9798§§100101§⌉.{\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}

El número cromático del plano, definido por la adyacencia entre puntos a una distancia unitaria, permanece indeterminado, aunque se sabe que es 5, 6 o 7. Problemas adicionales no resueltos relacionados con el número cromático de gráficos abarcan la conjetura de Hadwiger, que postula que cualquier gráfico con un número cromático de k contiene un gráfico completo en k vértices como menor. También se incluyen la conjetura de Erdős-Faber-Lovász, que establece un límite superior para el número cromático de uniones de grafos completos que comparten como máximo un vértice común por par, y la conjetura de Albertson, que sugiere que entre los grafos cromáticos k, los grafos completos exhiben el número de cruce mínimo.

Cuando Birkhoff y Lewis introdujeron el polinomio cromático como parte de sus esfuerzos por resolver el teorema de los cuatro colores, plantearon la hipótesis de que para gráficas planas ${\displaystyle G}$, el polinomio ${\displaystyle P(G,t)}$ no exhibiría ceros dentro del intervalo ${\displaystyle [4,\infty )}$. Si bien se establece que dicho polinomio cromático carece de ceros en la región ${\displaystyle [5,\infty )}$ y que P ( G , §106107§ ) ≠<!-- ≠ --> §113114§ {\displaystyle P(G,4)\neq 0} , su conjetura original sigue sin resolverse. Además, la caracterización de gráficos que poseen polinomios cromáticos idénticos y la identificación de qué polinomios son cromáticos siguen siendo problemas abiertos.

Algoritmos

Complejidad del tiempo polinomial

Determinar si un gráfico tiene dos colores es análogo a determinar su bipartición, una tarea que se puede lograr en tiempo lineal mediante algoritmos de búsqueda en amplitud o en profundidad. Para gráficos perfectos, el número cromático y una coloración asociada se pueden calcular dentro del tiempo polinómico utilizando programación semidefinida. Además, existen expresiones de forma cerrada para polinomios cromáticos para varias clases de gráficos, incluidos bosques, gráficos cordales, ciclos, ruedas y escaleras, lo que permite su evaluación en tiempo polinómico.

Cuando un gráfico es plano y exhibe un ancho de rama bajo, o si no es plano pero posee una descomposición de rama conocida, su polinomio cromático se puede determinar en tiempo polinómico mediante programación dinámica. Generalmente, el tiempo computacional escala polinomialmente con el tamaño del gráfico pero exponencialmente con su ancho de rama.

Algoritmos exactos

Un enfoque de fuerza bruta para encontrar una coloración k implica evaluar cada una de las ${\displaystyle k^{n}}$ posibles asignaciones de k colores a n vértices para verificar su legalidad. Para determinar el número cromático y el polinomio cromático, se debe aplicar este método para cada valor de ${\displaystyle k=1,\ldots ,n-1}$, lo que lo hace poco práctico excepto para los gráficos de entrada más diminutos.

La determinación de la colorabilidad k se puede lograr en la complejidad temporal y espacial de ${\displaystyle O(2.4423^{n})}$ mediante la aplicación de programación dinámica combinada con un límite en el número de conjuntos independientes máximos. Alternativamente, emplear el principio de inclusión-exclusión junto con el algoritmo de Yates para la transformada zeta rápida permite resolver la colorabilidad k en una complejidad temporal de O ( §4344§ n n ) {\displaystyle O(2^{n}n)} para cualquier valor de k. Existen algoritmos más eficientes para 3 colores y 4 colores, que se pueden decidir en complejidades temporales de O ( 1.3289 n ) {\displaystyle O(1.3289^n)} y ${\displaystyle O(1.7272^{n})}$, respectivamente. Además, hay disponibles algoritmos con rendimiento exponencialmente mejorado para 5 colores y 6 colores, así como para categorías específicas de gráficos, como gráficos dispersos.

Contracción

La operación de contracción, denotada como ${\displaystyle G/uv}$ para un gráfico G, implica fusionar vértices u y v en un único vértice nuevo, eliminando posteriormente cualquier borde que previamente conectara u y v. Los bordes originalmente incidentes con u o v se convierten en incidentes con este nodo fusionado recién formado, designado como uv. Esta operación fundamental es crítica en el análisis teórico de problemas de coloración de gráficos.

El número cromático se adhiere a la siguiente relación de recurrencia:

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

Esta relación fue establecida por Zykov en 1949, donde u y v representan vértices no adyacentes. La notación g + u v {\displaystyle G+uv} significa el gráfico formado sumando el borde uv a ${\displaystyle G+uv}$. Numerosos algoritmos aprovechan esta recurrencia y la estructura computacional derivada de su evaluación en ocasiones se denomina árbol de Zykov. La eficiencia de estos algoritmos depende de la heurística empleada para seleccionar los vértices u y v.

El polinomio cromático también se ajusta a la relación de recurrencia posterior:

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

Aquí, u y v denotan vértices adyacentes, y ${\displaystyle G-uv}$ representa el gráfico del que se ha eliminado el borde uv. Además, ${\displaystyle P(G-uv,k)}$ cuantifica el número de coloraciones propias distintas para el gráfico, donde a los vértices se les pueden asignar colores idénticos o distintos. En consecuencia, se puede conceptualizar que las coloraciones adecuadas surgen de dos configuraciones de gráficos distintas. Específicamente, si a los vértices u y v se les asignan colores diferentes, el escenario equivale a considerar un gráfico donde u y v son adyacentes. Por el contrario, si u y v comparten el mismo color, la situación se puede modelar mediante un gráfico donde u y v se contraen. La investigación de Tutte sobre otras propiedades gráficas que exhiben esta relación de recurrencia finalmente lo llevó a desarrollar el polinomio de Tutte, una generalización bivariada del polinomio cromático.

Estas formulaciones conducen a una metodología recursiva conocida como algoritmo de eliminación-contracción, que sustenta numerosos algoritmos de coloración de gráficos. La complejidad computacional de este algoritmo exhibe una relación de recurrencia análoga a la de los números de Fibonacci. En consecuencia, en el peor de los casos, su tiempo de ejecución está limitado por un factor polinómico de (§1617§+§2223§§2728§)n+m=O(1.6180n+m){\displaystyle \left({\tfrac {1+{\sqrt) {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}, donde n representa el número de vértices y m denota el número de aristas. Un análisis más detallado puede refinar este límite a un factor polinómico de ${\displaystyle t(G)}$, que indica el número de árboles de expansión en el gráfico de entrada. En aplicaciones prácticas, se emplean estrategias como bifurcación y límite, junto con el rechazo del isomorfismo gráfico, para mitigar el número de llamadas recursivas. El tiempo de ejecución real depende de la heurística elegida para seleccionar pares de vértices.

Coloración codiciosa

El algoritmo codicioso procesa los vértices en una secuencia predeterminada, específicamente de v §1011§ {\displaystyle v_{1}} a ${\displaystyle v_{n}}$. Para cada vértice ${\displaystyle v_{i}}$, el algoritmo asigna el color más bajo posible que no haya sido utilizado por ninguno de sus vecinos ya coloreados, específicamente aquellos dentro del conjunto v §9899§ {\displaystyle v_{1}} , ..., v i −<!-- − --> §125126§ {\displaystyle v_{i-1}} . Se introduce un nuevo color sólo si ningún color existente es adecuado. La eficacia de la coloración resultante depende del ordenamiento de vértices específico empleado. Si bien existe un orden óptimo que produce una coloración voraz con el número mínimo de colores, denotado como ${\displaystyle \chi (G)}$, los colorantes codiciosos también pueden funcionar arbitrariamente mal. Por ejemplo, un gráfico de corona con n vértices se puede colorear en 2 colores, pero un orden de vértices específico puede dar como resultado una coloración voraz que requiere ${\displaystyle n/2}$ colores.

En el contexto de los gráficos cordales, incluidos casos especializados como gráficos de intervalo y gráficos de indiferencia, el algoritmo de coloración codiciosa puede lograr coloraciones óptimas dentro del tiempo polinómico. Esto se logra seleccionando un orden de vértices que sea el inverso de un orden de eliminación perfecta para el gráfico. Si bien los gráficos perfectamente ordenables amplían esta característica, identificar un orden perfecto para estos gráficos es un problema NP-difícil.

Cuando los vértices se organizan según sus grados, la coloración codiciosa resultante emplea un máximo de max i min { d ( x i ) + §3839§ , i } {\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}} colores, que es como máximo un grado mayor que el grado máximo del gráfico. Esta heurística particular se conoce frecuentemente como algoritmo de Welsh-Powell. Por el contrario, una heurística propuesta por Brélaz determina dinámicamente el orden de los vértices durante la ejecución del algoritmo, priorizando la selección del vértice conectado a la mayor diversidad de colores. Muchas otras heurísticas de coloración de gráficos aprovechan de manera similar los principios de coloración codiciosa, empleando estrategias estáticas o dinámicas para el orden de los vértices. Estos métodos se conocen colectivamente como algoritmos de coloración secuencial.

El número de Grundy de un gráfico se define como el número máximo de colores que puede lograr el algoritmo codicioso, específicamente cuando se selecciona un orden de vértices para maximizar este recuento.

Algoritmos heurísticos

Entre las heurísticas de tiempo polinomial destacadas para colorear gráficos se encuentran el algoritmo DSatur y el algoritmo recursivo más grande primero (RLF).

El algoritmo DSatur, similar al método de coloración codiciosa, colorea secuencialmente los vértices del gráfico, utilizando un color novedoso sólo cuando es necesario. Después de la asignación de un color a un vértice, el algoritmo identifica el vértice no coloreado con el recuento máximo de colores distintos en su vecindad adyacente, coloreando posteriormente ese vértice. Esta métrica se denomina grado de saturación para un vértice específico.

Por el contrario, el algoritmo recursivo más grande primero (RLF) construye iterativamente cada clase de color. Este proceso implica identificar un conjunto máximo independiente de vértices dentro del gráfico mediante reglas heurísticas especializadas. A estos vértices identificados se les asigna el mismo color y posteriormente se eliminan del gráfico. Esta secuencia de operaciones se reitera en el subgrafo resultante hasta que se hayan coloreado todos los vértices.

La complejidad computacional en el peor de los casos para DSatur es {\displaystyle O(n^2)}, donde {\displaystyle n} denota el número total de vértices en el gráfico. Una implementación alternativa del algoritmo, que emplea un montón binario para gestionar los grados de saturación, logra una complejidad de {\displaystyle O((n+m)\log n)}, donde {\displaystyle m} representa el número de aristas. Este enfoque optimizado mejora significativamente el rendimiento de gráficos dispersos. En comparación, la complejidad general de RLF es ligeramente mayor que la de DSatur, registrada como {\displaystyle O(mn)}.

Tanto el algoritmo DSatur como el RLF producen soluciones exactas para gráficos bipartitos, cíclicos y de ruedas.

Algoritmos paralelos y distribuidos

Un gráfico cromático χ se puede colorear c dentro del modelo LOCAL determinista, lo que requiere {\displaystyle O(n^{1/\alpha) })} rondas, donde {\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }. Un límite inferior correspondiente de {\displaystyle \Omega (n^{1/\alpha })}. Este límite inferior sigue siendo válido incluso cuando se consideran sistemas de computación cuántica capaces de intercambiar información cuántica, aprovechando potencialmente un estado entrelazado previamente compartido.

Dentro del dominio de los algoritmos distribuidos, la coloración de gráficos muestra una fuerte correlación con el desafío de la ruptura de la simetría. Los algoritmos aleatorios contemporáneos demuestran una velocidad superior en comparación con los algoritmos deterministas cuando el grado máximo Δ es suficientemente grande. Los algoritmos aleatorios más eficientes aprovechan la técnica de ensayos múltiples desarrollada por Schneider y Wattenhofer.

En un gráfico simétrico, un algoritmo distribuido determinista no puede identificar una coloración de vértice adecuada. En consecuencia, se requiere información auxiliar para resolver la simetría. Una suposición común es que cada nodo posee inicialmente un identificador único, como el del conjunto {1, 2, ..., n}. Alternativamente, esto implica que inicialmente se proporciona una coloración n. El objetivo es reducir el número de colores de n a, por ejemplo, Δ + 1. Emplear un mayor número de colores, como O(Δ) en lugar de Δ + 1, generalmente requiere menos rondas de comunicación.

Una implementación distribuida directa del algoritmo codicioso para coloración (Δ + 1) exige Θ(n) rondas de comunicación en el peor de los casos, ya que es posible que la información deba propagarse por toda la red.

El escenario ilustrativo más simple implica un ciclo n. Richard Cole y Uzi Vishkin demostraron la existencia de un algoritmo distribuido que reduce el número de colores de n a O(log n) en un único paso de comunicación sincrónica. La aplicación repetida de este procedimiento permite lograr tres colores para un ciclo n en O(log* n) pasos de comunicación, siempre que haya identificadores de nodo únicos disponibles.

La función log*, conocida como logaritmo iterado, es una función de crecimiento excepcionalmente lento, a menudo considerada "casi constante". En consecuencia, los hallazgos de Cole y Vishkin impulsaron una investigación sobre la viabilidad de un algoritmo distribuido en tiempo constante para colorear con 3 colores un ciclo n. Linial (1992) demostró posteriormente la imposibilidad de esto, estableciendo que cualquier algoritmo distribuido determinista requiere Ω(log* n) pasos de comunicación para reducir una coloración n a una coloración de 3 dentro de un ciclo n.

La técnica desarrollada por Cole y Vishkin también es aplicable a gráficos arbitrarios de grados acotados, con un tiempo de ejecución de poli(Δ) + O(log* n). Schneider y Wattenhofer ampliaron esta técnica a gráficos de discos unitarios. Leonid Barenboim, Michael Elkin y Fabian Kuhn desarrollaron los algoritmos deterministas más rápidos para la coloración (Δ + 1) en casos de Δ pequeña. El algoritmo de Barenboim et al. opera dentro de una complejidad temporal de O(Δ) + log*(n)/2, que es óptima con respecto a n, ya que el factor constante de 1/2 no se puede mejorar dado el límite inferior establecido por Linial. Panconesi & Srinivasan (1996) utilizó descomposiciones de redes para calcular una coloración Δ+1 en el tiempo §2122§ O ( iniciar sesión ⁡ n ) {\displaystyle 2^{O\left({\sqrt {\log n}}\right)}} .

El problema de la coloración de los bordes se ha investigado de manera similar dentro del modelo distribuido. Panconesi & Rizzi (2001) logró una coloración (2Δ − 1) en tiempo O(Δ + log* n) utilizando este modelo. El límite inferior establecido por Linial (1992) para la coloración distribuida de vértices también es pertinente para el problema de la coloración distribuida de bordes.

Algoritmos descentralizados

Los algoritmos descentralizados funcionan sin pasar ningún mensaje, a diferencia de los algoritmos distribuidos, que dependen del intercambio de mensajes local. Se encuentran disponibles algoritmos descentralizados eficaces para colorear gráficos, siempre que sea posible realizar una coloración adecuada. Dichos algoritmos presuponen que un vértice puede detectar si alguno de sus vecinos emplea el mismo color, identificando así un conflicto local. Esta premisa se considera razonable en numerosas aplicaciones; por ejemplo, en la asignación de canales inalámbricos, normalmente es plausible suponer que una estación puede detectar otros transmisores que interfieren utilizando el mismo canal (por ejemplo, mediante medición SINR). Esta información sensorial es adecuada para que los algoritmos basados en autómatas de aprendizaje converjan en un color de gráfico adecuado con una probabilidad de uno.

Complejidad computacional

La complejidad computacional de la coloración de gráficos es significativa. Determinar si un gráfico dado permite una coloración k para un k específico es un problema NP-completo, con la excepción de los casos en los que k ∈ {0,1,2}. Específicamente, calcular el número cromático es una tarea NP-difícil. Incluso para gráficos planos de 4 regulares, el problema de 3 colores conserva su clasificación NP-completa. Por el contrario, para gráficos que poseen un grado máximo de 3 o menos, el teorema de Brooks demuestra que el problema de los 3 colores se puede resolver en tiempo lineal. Además, el teorema de los cuatro colores garantiza la existencia de una coloración k para cualquier gráfico plano cuando k > 3, y dicha coloración se puede identificar en tiempo polinomial. Sin embargo, la identificación de los 4 colores lexicográficamente más pequeños para un gráfico plano constituye un desafío NP-completo.

El algoritmo de aproximación más efectivo disponible actualmente produce un color cuyo tamaño está limitado por un factor de como máximo O(n(log log n)§67§(log n)⁻³) en relación con el cromático. número. Además, para cualquier ε > 0, que se aproxima al número cromático dentro de un factor de n^1−ε se clasifica como NP-duro.

Además, es NP-difícil colorear un gráfico de 3 colores usando 5 colores, un gráfico de 4 colores con 7 colores o un gráfico de k-colorable con ( k ⌊<!-- ⌊ --> k / §2829§ ⌋ ) − §4445§ {\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1} colores cuando k ≥ 5.

Determinar los coeficientes del polinomio cromático es un problema #P-difícil. De hecho, incluso calculando el valor de ${\displaystyle \chi (G,k)}$ demuestra ser #P-hard para cualquier valor racional de k, excluyendo k = 1 y k = 2. Además, no existe ningún esquema de aproximación aleatoria totalmente polinomial (FPRAS) para evaluar el polinomio cromático en cualquier punto racional k ≥ 1,5, con la única excepción de k = 2, a menos que las clases de complejidad NP y RP sean equivalentes.

Con respecto a la coloración de bordes, el teorema de Vizing proporciona una prueba que produce un algoritmo capaz de utilizar un máximo de Δ+1 colores. Sin embargo, la determinación entre los dos valores potenciales para el número cromático del borde es un problema NP-completo. En cuanto a los algoritmos de aproximación, el algoritmo de Vizing demuestra que el número cromático del borde se puede aproximar con una precisión de 4/3. Al mismo tiempo, un resultado de dureza correspondiente indica la inexistencia de cualquier algoritmo (4/3 − ε) para cualquier ε > 0, a menos que P sea igual a NP. Estos hallazgos representan algunas de las primeras contribuciones al campo de los algoritmos de aproximación, a pesar de que las publicaciones originales no emplearon explícitamente esta terminología específica.

Aplicaciones

Programación

La coloración de vértices sirve como modelo para varios problemas de programación. En su representación más sencilla, se debe asignar una colección específica de tareas a distintos intervalos de tiempo, y cada tarea exige un único intervalo. Si bien las tareas se pueden programar en cualquier secuencia, ciertos pares de tareas pueden estar en conflicto, lo que significa que no pueden ocupar el mismo intervalo de tiempo, a menudo debido a su dependencia de un recurso común. El gráfico resultante se construye con un vértice que representa cada tarea y un borde que conecta cada par de tareas en conflicto. El número cromático del gráfico corresponde precisamente al makespan mínimo, que significa la duración óptima requerida para completar todas las tareas sin conflictos.

Las características específicas de un problema de programación dictan la estructura del gráfico subyacente. Por ejemplo, en el contexto de la asignación de aeronaves a horarios de vuelo, el gráfico de conflicto generado es un gráfico de intervalo, lo que permite una resolución eficiente del problema de coloración. De manera similar, para la asignación de ancho de banda entre estaciones de radio, el gráfico de conflicto producido es un gráfico de disco unitario, lo que hace que el problema de coloración sea aproximado a 3.

Asignación de registros

Un compilador funciona como un programa de computadora diseñado para traducir el código fuente de un lenguaje de programación a otro. Para mejorar el rendimiento de ejecución del código generado, la optimización del compilador emplea técnicas como la asignación de registros, que implica almacenar los valores del programa compilado a los que se accede con más frecuencia dentro de los registros de alta velocidad del procesador. El escenario óptimo implica asignar valores a los registros de una manera que permita que todos los valores necesarios residan en los registros simultáneamente durante su uso.

En el diseño de compiladores, un enfoque convencional para este problema implica modelarlo como un problema de coloración de gráficos. Específicamente, el compilador genera un gráfico de interferencia, en el que las variables se representan como vértices y existe un borde entre dos vértices si sus variables correspondientes están activas simultáneamente. Si este gráfico se puede colorear con k colores distintos, implica que cualquier conjunto concurrente de variables se puede asignar a un máximo de k registros.

Más aplicaciones

Los problemas de coloración de gráficos se manifiestan en numerosos ámbitos prácticos, incluida la programación de deportes, el diseño de la disposición de los asientos, los horarios de exámenes, la optimización del despacho de taxis y la resolución de Sudokus.

Paradigmas de coloración alternativos

Teoría de Ramsey

La teoría de Ramsey investiga una categoría importante de problemas de coloración inadecuada, en los que los colores se asignan a los bordes de un gráfico sin imponer restricciones a los colores de los bordes incidentes. Una ilustración fundamental es el teorema sobre amigos y extraños, que postula que dentro de cualquier coloración de bordes de K §1213§ {\displaystyle K_6}, el gráfico completo que comprende seis vértices, se garantiza la existencia de un triángulo monocromático. Este concepto se ejemplifica frecuentemente al afirmar que cualquier grupo de seis individuos contendrá invariablemente tres extraños mutuos o tres conocidos mutuos. El alcance más amplio de la teoría de Ramsey implica generalizar este principio para identificar patrones dentro de una aparente aleatoriedad, estableciendo así condiciones universales para la presencia de subgrafos monocromáticos que poseen propiedades estructurales específicas.

Coloración modular

La coloración modular representa una categoría distinta de coloración de gráficos donde el color asignado a cada vértice está determinado por la suma de los colores de sus vértices vecinos.

Considere ${\displaystyle k\geq 2}$ como el número de colores disponibles, donde ${\displaystyle \mathbb {Z} _{k}}$ denota el conjunto de números enteros módulo k {\displaystyle k}, que comprende los elementos (o colores) §6768§ , §7172§ , §7576§ , . . . , k −<!-- − --> §9293§ , k −<!-- − --> §101102§ {\displaystyle 0,1,2,...,k-2,k-1} . Inicialmente, cada vértice dentro del gráfico G {\displaystyle G} A se le asigna un color del conjunto Z k {\displaystyle \mathbb {Z} _k}, sin restricción que impida que los vértices adyacentes compartan el mismo color. En consecuencia, el objetivo es definir una función de coloración c {\displaystyle c} tal que ${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$, donde se permite la asignación de colores idénticos a vértices adyacentes.

Para cada vértice ${\displaystyle v}$ dentro de un gráfico ${\displaystyle G}$, su suma de colores, denotada como ${\displaystyle v}$, o más formalmente ${\displaystyle \sigma (v)}$, representa la suma de los colores de todos los vértices adyacentes a ${\displaystyle v}$, módulo calculado ${\displaystyle k}$. Esta suma de colores para ${\displaystyle v}$ se expresa formalmente como:

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

Aquí, ${\displaystyle u}$ denota cualquier vértice dentro de la vecindad de ${\displaystyle v}$, representado como N(v){\displaystyle N(v)}. Posteriormente, a cada vértice se le asigna un nuevo color en función de la suma de los colores de sus vértices adyacentes. Un gráfico ${\displaystyle Se considera que G}$ posee un ${\displaystyle k}$-colorear si, para cualquier par de vértices adyacentes, como ${\displaystyle a}$ y ${\displaystyle b}$, sus respectivas sumas de colores son distintas, es decir, ${\displaystyle \sigma (a)\neq \sigma (b)}$.El número cromático modular de ${\displaystyle G}$, indicado como ${\displaystyle mc(G)}$, se define como el entero más pequeño valor de ${\displaystyle k}$ para el cual un modular ${\displaystyle k}$-coloración de ${\displaystyle G}$ existe.

Considere un vértice ${\displaystyle v}$ con vértices adyacentes asignados a los colores §2223§ , §2627§ , §3031§ {\displaystyle 0,1,1} y ${\displaystyle 3{\bmod {4}}}$ (donde k = §7475§ {\displaystyle k=4}). La suma de colores resultante se calcula como σ<!-- σ --> ( v ) = ( §103104§ + §107108§ + §111112§ + §115116§ ) mod §123124§ = §129130§ mod §135136§ = §141142§ mod §147148§ {\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}} . Este valor luego se convierte en el nuevo color del vértice v {\displaystyle v}. Este proceso iterativo se aplica a cada vértice dentro de G {\displaystyle G}.Si ningún vértice adyacente posee sumas de colores idénticas, entonces ${\displaystyle G}$ se considera que tiene un módulo ${\displaystyle 4}$ colorear.

Metodologías de coloración alternativas

El concepto de colorear se extiende a gráficos con signos y gráficos de ganancias.

Gráfico crítico

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

Notas

Referencias

GCol: una biblioteca Python de código abierto diseñada para colorear gráficos.

• GCol Una biblioteca de Python de código abierto para colorear gráficos.
• Algoritmos de coloración de gráficos de alto rendimiento: una colección de ocho algoritmos distintos (implementados en C++) que aparecen en la publicación Una guía para la coloración de gráficos: algoritmos y aplicaciones (Springer International Publishers, 2015).
• CoLoRaTiOn de Jim Andrews y Mike Fellows constituye un rompecabezas para colorear gráficos.
• Código fuente para el cálculo eficiente de polinomios Tutte, cromáticos y de flujo por Gary Haggard, David J. Pearce y Gordon Royle.
• Código para calcular eficientemente 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 desarrollada por José Antonio Martín H.