LISTA DE PROBLEMAS

COLORACIÓN DE GRÁFICOS , CONTINUACIÓN I

Propiedades [ editar ]

Límites en el número cromático [ editar ]

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

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

Los únicos gráficos que pueden ser de 1 color son gráficos sin bordes . 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 uno de los bordes m del gráfico entre cada par de clases de color, por lo que

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

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

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

Para gráficos perfectos, este límite es ajustado. Encontrar camarillas se conoce como problema de camarilla .

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

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

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

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

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

Límites inferiores en el número cromático [ editar ]

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

El límite de Hoffman: Let$${\ displaystyle W} ser una matriz simétrica real tal que $${\ displaystyle W_ {i, j} = 0} cuando $${\ 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$${\ displaystyle \ chi _ {H} (G) = \ max _ {W} \ chi _ {W} (G)}, con $${\ displaystyle W}como anteriormente. Luego:

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

Número cromático del vector : Let$${\ displaystyle W} ser una matriz semi-definida positiva tal que $${\ displaystyle W_ {i, j} \ leq - {\ tfrac {1} {k-1}}} cuando $${\ displaystyle (i, j)} es una ventaja en $${\ displaystyle G}. Definir$${\ displaystyle \ chi _ {V} (G)} ser el menor k para el cual dicha matriz $${\ displaystyle W}existe Luego

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

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

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

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

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

Estos límites se ordenan de la siguiente manera:

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

Gráficos con alto número cromático [ editar ]

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

Teorema de Mycielski ( Alexander Zykov  1949 , Jan Mycielski  1955 ): existen gráficos libres de triángulos con un número cromático arbitrariamente alto.

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

Teorema (Erdős): existen gráficos de circunferencia arbitrariamente alta y número cromático ^[5] .

Límites en el índice cromático [ editar ]

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

$${\ 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)}. Como todos los bordes incidentes con el 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 aún más fuerte que la que da el teorema de Brooks para la coloración de vértices:

Teorema de Vizing: una gráfica de grado máximo$${\ displaystyle \ Delta} tiene número de borde cromático $${\ displaystyle \ Delta} o $${\ displaystyle \ Delta +1}.

Otras propiedades [ editar ]

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

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

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

• Si todas las subgrafías finitas de un gráfico infinito G son k -colorables, entonces también lo es G , bajo el supuesto del axioma de elección . Este es el teorema de De Bruijn-Erd de De Bruijn y Erdős (1951) .
• Si un gráfico admite un color n completo por cada n ≥ n ₀ , admite un color completo infinito ( Fawcett 1978 ).

Problemas abiertos [ editar ]

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 .}$

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

Cuando Birkhoff y Lewis introdujeron el polinomio cromático en su ataque al teorema de los cuatro colores, conjeturaron que para los gráficos planos G , el polinomio$${\ 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 sigue sin resolverse. También sigue siendo un problema sin resolver caracterizar gráficos que tienen el mismo polinomio cromático y determinar qué polinomios son cromáticos.

Algoritmos [ editar ]

Coloración gráfica
Decisión
Nombre	Graph colorante, colorante vértice, k -Coloreado
Entrada	Grafica G con n vértices. Entero k
Salida	¿ Admite G una coloración de vértice adecuada con k colores?
Tiempo de ejecución	O (2 n n ) [6]
Complejidad	NP-complete
Reducción de	3-satisfacción
Garey – Johnson	GT4
Mejoramiento
Nombre	Número cromático
Entrada	Grafica G con n vértices.
Salida	χ ( G )
Complejidad	NP-hard
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
Entrada	Grafica G con n vértices. Entero k
Salida	El número P  ( G , k ) de colorantes k propios de G
Tiempo de ejecución	O (2 n n )
Complejidad	# P-completo
Aproximabilidad	FPRAS para casos restringidos
Inaproximabilidad	Sin PTAS a menos que P = NP

Tiempo polinómico [ editar ]

Determinar si un gráfico puede ser coloreado con 2 colores es equivalente a determinar si el gráfico es o no bipartito , y por lo tanto computable en tiempo lineal usando la búsqueda de amplitud primero o la búsqueda de profundidad primero . De manera más general, el número cromático y una coloración correspondiente de gráficos perfectos se pueden calcular en tiempo polinómico usando programación semidefinida . Las fórmulas cerradas para polinomios cromáticos son conocidas para muchas clases de gráficos, como bosques, gráficos cordales, ciclos, ruedas y escaleras, por lo que estos pueden evaluarse en tiempo polinómico.

Si el gráfico es plano y tiene un ancho de rama bajo (o no es plano pero tiene una descomposición de rama conocida), entonces puede resolverse 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 la rama.

Algoritmos exactos [ editar ]

La búsqueda de fuerza bruta para un k- coloring considera cada uno de los$${\ displaystyle k ^ {n}}asignaciones de k colores a n vértices y verifica para cada uno si es legal. 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 para todos los gráficos de entrada, excepto los más pequeños.

Usando programación dinámica y un límite en el número de conjuntos independientes máximos , la capacidad de coloración k se puede decidir en tiempo y espacio$${\ displaystyle O (2.445 ^ {n})}. ^[7] Utilizando el principio de inclusión-exclusión y el algoritmo de Yates para la transformación rápida zeta, la capacidad de coloración k se puede decidir a tiempo$${\ displaystyle O (2 ^ {n} n)}^[6] para cualquier k . Se conocen algoritmos más rápidos para la colorabilidad 3 y 4, que se pueden decidir a tiempo$${\ displaystyle O (1.3289 ^ {n})}^[8] y$${\ displaystyle O (1.7272 ^ {n})}, ^[9] respectivamente.

Contracción [ editar ]

La contraccion $${\ displaystyle G / uv}de un gráfico G es el gráfico obtenido al identificar los vértices u y v , y eliminar cualquier borde entre ellos. Los bordes restantes originalmente incidente a U o V son ahora incidente a su identificación. Esta operación juega un papel importante en el análisis de la coloración de gráficos.

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 gráfico con el borde uv agregado. Varios algoritmos se basan en la evaluación de esta recurrencia y el árbol de cálculo resultante a veces se denomina árbol de Zykov. El tiempo de ejecución se basa en una heurística para elegir los vértices u y v .

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 borde uv eliminado.$${\ displaystyle P (G-uv, k)}representa el número de posibles colores adecuados del gráfico, donde los vértices pueden tener los mismos o diferentes colores. Luego, los colores adecuados surgen de dos gráficos diferentes. Para explicar, si los vértices u y v tienen colores diferentes, entonces también podríamos considerar un gráfico donde u y v son adyacentes. Si u y v tienen los mismos colores, también podríamos considerar un gráfico donde se contraigan u y v . La curiosidad de Tutte sobre qué otras propiedades gráficas satisfacían esta recurrencia lo llevó a descubrir una generalización bivariada del polinomio cromático, el polinomio de Tutte .

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

Coloración codiciosa [ editar ]

Artículo principal: coloración codiciosa

Dos colores codiciosos del mismo gráfico usando diferentes órdenes de vértices. El ejemplo correcto generaliza a gráficos de 2 colores con n vértices, donde el algoritmo codicioso gasta$${\ displaystyle n / 2} colores.

El algoritmo codicioso 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}}los vecinos entre $${\ displaystyle v_ {1}}, ...,$${\ displaystyle v_ {i-1}}, agregando un color fresco si es necesario. La calidad del color resultante depende del orden elegido. Existe un orden que conduce a una coloración codiciosa con el número óptimo de$${\ displaystyle \ chi (G)}colores. Por otro lado, los colores codiciosos pueden ser arbitrariamente malos; por ejemplo, el gráfico de la corona en n vértices puede ser de 2 colores, pero tiene un orden que conduce a un color codicioso con$${\ displaystyle n / 2} colores.

Para los gráficos cordales , y para casos especiales de gráficos cordales, como los gráficos de intervalos y los gráficos de indiferencia , el algoritmo de coloración codicioso se puede utilizar para encontrar coloraciones óptimas en el tiempo polinómico, eligiendo el orden de vértices como el reverso de un orden de eliminación perfecto para el grafico. Los gráficos perfectamente ordenables generalizan esta propiedad, pero es NP-difícil encontrar un orden perfecto de estos gráficos.

Si los vértices se ordenan de acuerdo con sus grados , la coloración codiciosa 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 gráfico. Esta heurística a veces se llama algoritmo galés-Powell. ^[12] Otra heurística debido a Brélaz establece el orden dinámicamente mientras el algoritmo continúa, eligiendo a continuación el vértice adyacente al mayor número de colores diferentes. ^[13] Muchas otras heurísticas de coloración de gráficos se basan de manera similar en la coloración codiciosa para una estrategia estática o dinámica específica de ordenar los vértices, estos algoritmos a veces se denominan algoritmos de coloración secuenciales .

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

Algoritmos paralelos y distribuidos [ editar ]

En el campo de los algoritmos distribuidos , la coloración de gráficos está estrechamente relacionada con el problema de la ruptura de simetría . Los algoritmos aleatorizados de vanguardia 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 et al. ^[14]

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

Una versión distribuida directa del algoritmo codicioso para la coloración (Δ + 1) requiere rondas de comunicación Θ ( n ) en el peor de los casos; la información puede necesitar propagarse de un lado de la red a otro lado.

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

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

La técnica de Cole y Vishkin también se puede aplicar en gráficos arbitrarios de grado acotado; el tiempo de ejecución es poli (Δ) + O ( log *  n ). ^[16] La técnica se extendió a los gráficos de unidades de disco por Schneider et al. ^[17] 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. ^[18] El algoritmo de Barenboim et al. se ejecuta en el tiempo O (Δ) +  log * ( n ) / 2, que es óptimo en términos de n ya que el factor constante 1/2 no puede mejorarse debido al límite inferior de Linial.Panconesi y Srinivasan (1996) usan 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 del borde también se ha estudiado en el modelo distribuido. Panconesi y Rizzi (2001) logran una coloración (2Δ - 1) en el tiempo O (Δ +  log *  n ) en este modelo. El límite inferior para la coloración de vértices distribuidos debido a Linial (1992) se aplica también al problema de coloración de bordes distribuidos.

Algoritmos descentralizados [ editar ]

Los algoritmos descentralizados son aquellos en los que no se permite el paso de mensajes (en contraste con los algoritmos distribuidos donde tiene lugar el paso de mensajes locales), y existen algoritmos descentralizados eficientes que colorearán un gráfico si existe un color adecuado. 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 moderada en muchas aplicaciones, por ejemplo, en la asignación de canales inalámbricos, generalmente es razonable suponer que una estación podrá detectar si otros transmisores interferentes están usando el mismo canal (por ejemplo, midiendo el SINR). Esta información de detección es suficiente para permitir que los algoritmos basados ​​en autómatas de aprendizaje encuentren una coloración gráfica adecuada con probabilidad uno. ^[19]

Complejidad computacional [ editar ]

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

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. ^[22] Para todos ε  > 0, aproximar el número cromático dentro de n ^1− ε es NP-duro . ^[23]

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

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

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

Aplicaciones [ editar ]

Programación [ editar ]

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

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

Registrar asignación [ editar ]

Artículo principal: Asignación de registro

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

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

Otras aplicaciones [ editar ]

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

Otros colores [ editar ]

Teoría de Ramsey [ editar ]

Artículo principal: teoría de Ramsey

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

Otros colores [ editar ]

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

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

La coloración también se puede considerar para gráficos firmados y gráficos de ganancia .