Coloración uniforme

La coloración uniforme  es la asignación de colores a los vértices de un grafo no dirigido de tal forma que:

Es decir, dividir los vértices en diferentes colores es lo más uniforme posible. Por ejemplo, dar a cada vértice un color diferente sería una coloración uniforme, pero normalmente usaría muchos más colores de los necesarios para una coloración uniforme óptima. Una forma equivalente de definir un color uniforme es incrustar un gráfico dado como subgráfico en un gráfico de Turan con el mismo conjunto de vértices. Hay dos tipos de números cromáticos asociados con la coloración uniforme [1] . El número cromático uniforme de un grafo G  es el número más pequeño k tal que el grafo G tiene una coloración uniforme con k colores. Sin embargo, el gráfico G puede no tener colores uniformes para algunos conjuntos de colores más grandes. El umbral cromático uniforme de un gráfico G  es el número k más pequeño tal que el gráfico G tiene coloraciones uniformes para cualquier número de colores mayor o igual que k [2] .

El teorema de Hajnal-Szemeredy , que fue formulado como una conjetura por Pal Erdős [3] y demostrado por András Hajnal y Endre Szemeredy [4] , establece que cualquier gráfico con un grado máximo tiene una coloración uniforme con colores. Varias hipótesis relacionadas permanecen abiertas. También hay algoritmos de tiempo polinomial para encontrar un color correspondiente a este límite [5] , así como algoritmos para encontrar colores óptimos para clases especiales de gráficos, pero un problema más general de determinar si un gráfico arbitrario tiene un color uniforme con un determinado el número de colores es NP-completo .

Ejemplos

La estrella K 1.5 que se muestra en la figura es un gráfico bipartito completo y, por lo tanto, se puede colorear con dos colores. Sin embargo, la coloración resultante tiene un vértice de un color y cinco vértices de otro color y, por lo tanto, la coloración no es uniforme. El número más pequeño de colores en una coloración uniforme de este gráfico es cuatro, como se muestra en la figura: el vértice central debe pertenecer a una clase con un solo vértice, por lo que los otros cinco vértices deben dividirse en al menos tres colores para que cada uno La clase contiene como máximo dos vértices. De manera más general, Meyer [6] señaló que cualquier estrella K 1, n requiere colores para una coloración uniforme y, por lo tanto, el número cromático de un gráfico puede diferir de su número cromático uniforme en no más de n /4 veces. Como K 1,5 tiene un grado máximo de cinco, el número de colores garantizado por el teorema de Hajnal-Szemeredi es seis, que se obtiene asignando un color diferente a cada vértice.

Otro fenómeno interesante muestra otro gráfico bipartito completo, . Este gráfico tiene una coloración uniforme de 2 definida por su bipartito. Sin embargo, no tiene una coloración uniforme (2 n  + 1): cualquier partición uniforme de vértices en este número de colores tendría que tener exactamente dos vértices por color, pero las dos partes de un gráfico bipartito no se pueden emparejar porque contienen un número impar de vértices. Por tanto, el umbral cromático uniforme de este gráfico es , que es mucho mayor que su número cromático uniforme, que es dos.

El teorema de Hainal-Semeredi

El teorema de Brooks establece que cualquier gráfico conexo con grado máximo es -coloreable, con dos excepciones ( gráficos completos y ciclos impares). Sin embargo, esta coloración en general puede estar lejos de ser uniforme. Pal Erdős [3] conjeturó que es posible una coloración uniforme con un solo color complementario: cualquier gráfico con grado máximo tiene una coloración uniforme con colores. El caso es sencillo (cualquier combinación de rutas y bucles se puede colorear de manera uniforme con patrones repetitivos de tres colores, con ligeros ajustes para bucles cerrados). El caso fue decidido por Corradi y Hainal [7] . La conjetura completa fue probada por Hajnal y Semeredi [4] y ahora se conoce como el teorema de Hajnal-Szemeredi. Su prueba original era larga y complicada. Kirsted y Kostochka [8] dieron una demostración más sencilla . Kiersted y Kostochka describieron un algoritmo de tiempo polinomial para encontrar coloraciones uniformes con este número de colores. Atribuyen a Marcelo Midlarz y Endre Szemeredi un algoritmo de tiempo polinomial diferente, previamente desarrollado e inédito. Kiersted y Kostochka también anunciaron una versión más fuerte del teorema de que existe una coloración uniforme de k si los grados de dos vértices adyacentes suman como máximo , pero la prueba nunca se publicó.

Meyer [6] conjeturó en la forma del teorema de coloración uniforme de Brooks que cualquier gráfico conectado con grado máximo tiene una coloración uniforme con o menos colores, excepto para gráficos completos y ciclos impares. Una versión más fuerte de la conjetura establece que cada gráfico tiene una coloración uniforme con colores exactos, con la excepción adicional de un gráfico bipartito completo en el que ambas partes tienen el mismo número impar de vértices [1] .

Seymour [9] propuso un refuerzo del teorema de Hajnal-Szemeredi, que también incluye el teorema de Dirac de que los grafos densos son hamiltonianos  : conjeturó que si cualquier vértice en un grafo con n vértices tiene al menos vecinos, entonces el grafo contiene como subgrafo el gráfico formado por la conexión de vértices que están a lo sumo k pasos de distancia en un ciclo de n . El caso k  = 1 es el propio teorema de Dirac. El teorema de Hajnal-Szemeredi puede ser anulado por esta hipótesis aplicando la hipótesis para valores grandes de k al complemento del gráfico y usando secuencias continuas de vértices del ciclo n como clases de color . La conjetura de Seymour se ha probado para gráficos donde n es lo suficientemente grande en comparación con k [10] . La prueba utiliza algunos medios profundos, incluido el propio teorema de Hajnal-Szemeredi.

Otra generalización del teorema de Haynal-Szemeredi es la hipótesis de Bollobash-Eldridge-Katlin (o, para abreviar, la hipótesis BEC) [11] . Establece que si G 1 y G 2 son grafos de n -vértices con grado máximo y respectivamente, y si , entonces G 1 y G 2 pueden empaquetarse. Es decir, G 1 y G 2 se pueden representar en el mismo conjunto de n vértices sin aristas comunes. El teorema de Hajnal-Szemeredi es un caso especial de la conjetura en la que G 2 es la unión de camarillas disjuntas . Catlin [12] da una condición similar pero más fuerte sobre y bajo la cual se garantiza que existe tal empaquetadura.

Casos especiales de grafos

Para cualquier árbol con grado máximo, el número cromático uniforme no excede

[6]

con el peor de los casos en una estrella. Sin embargo, la mayoría de los árboles tienen un número cromático uniforme mucho más pequeño: si un árbol con n vértices tiene , entonces tiene una coloración uniforme con solo tres colores [13] . Furmanchik [1] estudió el número cromático uniforme de productos de grafos .

Complejidad computacional

También se estudió el problema de encontrar coloraciones uniformes con la menor cantidad de colores posible (por debajo del límite Hainal-Semeredi). Se puede probar una reducción directa de la coloración de un gráfico a una coloración uniforme agregando suficientes vértices aislados al gráfico, lo que muestra que probar si un gráfico tiene un color uniforme con un número dado de colores (más de dos) es NP-completo . Sin embargo, el problema se vuelve más interesante cuando se restringe a una clase especial de grafos o en términos de complejidad parametrizada . Bodlander y Fomin [14] demostraron que dado un gráfico G y un número de colores c , se puede verificar si G puede tener un color c uniforme en el tiempo O( n O( t ) ), donde t  es el ancho del árbol de G . En particular, la coloración uniforme se puede resolver de manera óptima en tiempo polinomial para árboles (como se sabe gracias a Chen y Lee [15] ) y grafos planos exteriores . También hay un algoritmo de tiempo polinomial para la coloración uniforme de gráficos divididos [16] . Sin embargo, Fellowes, Fomin, Lokshtanov y otros [17] demostraron que cuando el ancho del árbol es un parámetro del algoritmo, el problema es W[1]-difícil. Por lo tanto, es poco probable que exista un algoritmo de tiempo polinomial que sea independiente de este parámetro, o incluso que la dependencia del parámetro pueda estar entre paréntesis por el exponente en la fórmula del tiempo de ejecución.

Aplicaciones

Una de las razones para considerar la coloración uniforme fue sugerida por Meyer [6] en relación con los problemas de programación . En esta aplicación, los vértices del gráfico representan un conjunto de tareas a realizar y los bordes conectan dos tareas que no se pueden realizar al mismo tiempo. El coloreado de este gráfico representa la división de tareas en subconjuntos que se pueden ejecutar simultáneamente. Luego, la cantidad de colores en el colorante corresponde a la cantidad de pasos necesarios para completar la tarea por completo. De acuerdo con las convenciones de balanceo de carga , es deseable realizar el mismo o casi el mismo número de tareas en cada paso, y este balanceo es exactamente lo que da el coloreado uniforme. Furmanchik [1] mencionó una aplicación específica de este tipo de problema de programación, a saber, la distribución de cursos universitarios por horas académicas de modo que los cursos se distribuyan equitativamente en los intervalos de tiempo disponibles, con el fin de evitar asignar pares de cursos incompatibles al mismo tiempo.

El teorema de Hajnal-Szemeredi también se ha utilizado para limitar la varianza de sumas de variables aleatorias con dependencia acotada [18] [19] . Si (como en la condición del lema local de Lovas ) cada variable depende como máximo de otras, se puede usar una coloración uniforme del gráfico de dependencia para dividir las variables en subconjuntos independientes dentro de los cuales se pueden calcular los límites de Chernoff , lo que dará mejores límites en la varianza que si se repartiera de forma no uniforme.

Notas

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Tenga en cuenta que cuando k es mayor que el número de vértices en el gráfico, siempre hay una coloración uniforme con k colores en el que todas las clases de color tienen cero o un vértice por clase, por lo que cualquier gráfico tiene un umbral cromático uniforme.
  3. ↑ 12 Erdös , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , pág. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobas, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobas, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Becarios, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Rucinski, 2002 .

Literatura

Enlaces