Colorante prescrito

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2022; las comprobaciones requieren 5 ediciones .

Una coloración prescrita  es un tipo de coloración de gráfico en el que cada vértice puede adoptar un conjunto limitado de colores permitidos. Weesing y Erdős fueron de los primeros en estudiar esta coloración , así como Rubin y Taylor [1] en la década de 1970.

Definición

Dado un gráfico G y un conjunto L ( v ) de colores válidos para cada vértice de V (llamado lista ), la coloración prescrita  es una función de selección que asigna cada vértice de V a una lista L(v) . Al igual que con la coloración de gráficos, se supone que la coloración prescrita es correcta , lo que significa que no hay dos vértices adyacentes que reciban el mismo color. Se dice que un gráfico es k -elegible (o prescrito -k -coloreable ) si tiene la coloración prescrita correcta, independientemente de cómo se asignen los k colores a cada vértice. El número de elección ( colorabilidad prescrita o número cromático prescrito ) ch( G ) de un gráfico G  es el número más pequeño k tal que G es k -elegible.

Más generalmente, si se da una función f que asigna un número positivo f ( v ) a cada vértice v , se dice que un grafo G es f -elegible (o prescrito -f - coloreable ) si tiene un color prescrito independientemente de cómo el enumera los colores f ( v ) para cada vértice v . En particular, si para todos los vértices v , f -selectividad corresponde a k -selectividad.

Ejemplos

Considere un gráfico bipartito completo con seis vértices A , B , W , X , Y , Z , tal que A y B están conectados a cada uno de los vértices W , X , Y y Z y no hay otros bordes. En cuanto a cualquier gráfico bipartito, el número cromático habitual del gráfico G es 2: puede colorear los vértices A y B con un color, y los vértices restantes ( W , X , Y , Z ) con otro color, entonces no habrá dos adyacentes. tener el mismo color. Por otro lado, G tiene un número cromático prescrito mayor a 2, lo cual se muestra mediante la siguiente construcción: Asignar a los vértices A y B las listas {rojo, azul} y {verde, negro}. Asigna las listas {rojo, verde}, {rojo, negro}, {azul, verde} y {azul, negro} a los otros cuatro vértices. No importa qué elección se haga de las listas para los vértices A y B , porque hay algunos otros vértices para los que ya se han usado ambos colores en la lista. Por lo tanto, el gráfico G no es 2-elegible.

Por otro lado, es fácil ver que G es de 3 opciones: elegir cualquier color para los vértices A y B deja al menos un color válido para cada vértice restante.

De manera más general, sea q un número entero positivo y G un gráfico bipartito completo . Dejemos que los colores permitidos sean representados por diferentes números de dos dígitos en el sistema radix q (es decir, en el sistema q -ario). Deje que una parte, a saber, la parte con q vértices, tenga conjuntos de colores s en los que los primeros signos son iguales para cada elección de q posibilidades de elegir el dígito i . La otra parte del gráfico de vértices se da con colores , por lo que el primer dígito es diferente para cualquier conjunto de q elementos. La ilustración muestra un ejemplo de tal construcción con q  = 3.

Entonces G no tiene un color prescrito para L  ; no importa qué conjunto de colores se elija para los vértices en el lado más pequeño del gráfico bipartito, esta elección entrará en conflicto con todos los colores para un vértice en el otro lado del gráfico bipartito. Por ejemplo, si un vértice con el conjunto de colores {00,01} tiene el color 01 y un vértice con el conjunto de colores {10,11} tiene el color 10, entonces un vértice con el conjunto de colores {01,10} no se puede colorear correctamente. Por lo tanto, el número cromático de G es al menos [2] .

De manera similar, si , entonces el grafo bipartito completo no es k -elegible. Para mostrar esto, supongamos que hay un total de colores disponibles, de modo que en un lado del gráfico bipartito, cada vértice tiene un conjunto diferente de k colores para cada vértice. Luego, cada lado del gráfico bipartito usa al menos k colores para colorear. En caso contrario, debe existir un vértice en el que el conjunto de colores sea diferente al utilizado. Dado que se usan al menos k colores en un lado y al menos k en el otro, debe haber un color que se use en ambos lados, pero se sigue que dos vértices adyacentes tienen el mismo color. En particular, el grafo comunal tiene un número cromático prescrito no menor de tres, y el grafo tiene un número cromático prescrito no menor de cuatro [3] .

Propiedades

Para un grafo G , denotemos el número cromático y la potencia máxima del grafo G. El número de colorantes prescritos satisface las siguientes propiedades:

  1. . Un grafo que permita una k -coloración prescrita debe, en particular, tener una coloración prescrita si a cada vértice se le asigna la misma lista de k colores, que corresponde a la k -coloración habitual;
  2. no puede limitarse en general en términos del número cromático, es decir, no hay una función f tal que se cumpla para cualquier gráfico G . En particular, como se muestra en los ejemplos de grafos bipartitos, hay grafos con , para los cuales arbitrariamente grande [2] ;
  3. , donde n es el número de vértices del grafo G [4] [4] ;
  4. [3] [5] ;
  5. , si G es un grafo plano [6] ;
  6. , si G es un grafo plano bipartito [7] .

Cálculo de selectividad y ( a , b )-selectividad

Dos problemas algorítmicos son considerados en la literatura:

  1. k - seleccionabilidad : determinar si un gráfico dado es k -seleccionable para un k dado;
  2. ( a , b ) -seleccionabilidad : determina si un gráfico dado es f -seleccionable para una función dada .

Se sabe que el problema de k -selectividad en gráficos bipartitos es completo para cualquier y lo mismo es cierto para 4-selectividad en gráficos planos, 3-selectividad en gráficos planos sin triángulos y (2, 3)-selectividad en gráficos bipartitos planos gráficos [8] [9] . Para gráficos sin P5, es decir, gráficos sin rutas de 5 vértices , la seleccionabilidad k es un problema solucionable de parámetro fijo [10] .

Es posible verificar si un gráfico es seleccionable en 2 en tiempo lineal eliminando secuencialmente vértices con grado cero o unidad hasta que obtengamos un núcleo 2 del gráfico, después de lo cual tales eliminaciones se vuelven imposibles. El gráfico original se elige en 2 si y solo si su núcleo de 2 es un ciclo par o un gráfico theta formado por tres caminos con puntos finales comunes, dos caminos de longitud dos y el tercer camino puede tener cualquier longitud par [3] .

Aplicaciones

El colorido prescrito surge en problemas prácticos relacionados con la asignación de canales de frecuencia [11] [12] .

Véase también

Notas

  1. ↑ Jensen, Toft, 1995 , pág. 18–21.
  2. ↑ 1 2 Gravier, 1996 , pág. 299–302.
  3. ↑ 1 2 3 Erdős, Rubin, Taylor, 1979 , p. 125–157.
  4. ↑ 12 Eaton , 2003 .
  5. ↑ Vising, 1976 , pág. 3–10.
  6. ↑ Thomassen, 1994 , pág. 180–181.
  7. ↑ Alon, Tarsi, 1992 , pág. 125-134.
  8. ↑ Gutner, 1996 , pág. 119–130.
  9. ↑ Gutner, Tarsi, 2009 , pág. 2260–2270.
  10. ↑ Heggernes y Golovach, 2009 , p. 382–391.
  11. ↑ Wang, Liu, 2005 , pág. 690–694.
  12. ↑ Garg, Papatriantafilou y Tsigas, 1996 , p. 18–25.

Literatura

Lectura para leer más