En teoría de grafos , un área de las matemáticas, una coloración equitativa es una asignación de colores a los vértices de un grafo no dirigido , de tal manera que
Es decir, la partición de vértices entre los distintos colores sea lo más uniforme posible. Por ejemplo, dar a cada vértice un color distinto sería equitativo, pero normalmente utilizaría muchos más colores de los necesarios para una coloración equitativa óptima. Una forma equivalente de definir una coloración equitativa es que es una incrustación del gráfico dado como un subgrafo de un gráfico de Turán con el mismo conjunto de vértices. Hay dos tipos de números cromáticos asociados con la coloración equitativa. [1] El número cromático equitativo de un gráfico G es el número más pequeño k tal que G tiene una coloración equitativa con k colores. Pero es posible que G no tenga coloraciones equitativas para un número mayor de colores; el umbral cromático equitativo de G es el k más pequeño tal que G tiene coloraciones equitativas para cualquier número de colores mayor o igual a k . [2]
El teorema de Hajnal-Szemerédi , planteado como una conjetura por Paul Erdős (1964) y demostrado por András Hajnal y Endre Szemerédi (1970), establece que cualquier gráfico con grado máximo Δ tiene una coloración equitativa con Δ + 1 colores. Varias conjeturas relacionadas siguen abiertas. Los algoritmos de tiempo polinómico también son conocidos por encontrar una coloración que coincida con este límite [3] y por encontrar coloraciones óptimas de clases especiales de gráficos, pero el problema más general de decidir si un gráfico arbitrario tiene una coloración equitativa con un número determinado de colores es NP-completo .
La estrella K 1,5 que se muestra en la ilustración es un gráfico bipartito completo y, por tanto, se puede colorear con dos colores. Sin embargo, la coloración resultante tiene un vértice en una clase de color y cinco en otra y, por lo tanto, no es equitativa. El número más pequeño de colores en una coloración equitativa de este gráfico es cuatro, como se muestra en la ilustración: el vértice central debe ser el único vértice en su clase de color, por lo que los otros cinco vértices deben dividirse entre al menos tres clases de color en orden. para garantizar que las otras clases de colores tengan como máximo dos vértices. De manera más general, Meyer (1973) observa que cualquier estrella K 1, n necesita colores de cualquier coloración equitativa; por tanto, el número cromático de un gráfico puede diferir de su número de coloración equitativo en un factor tan grande como n /4. Debido a que K 1,5 tiene un grado máximo de cinco, el número de colores que le garantiza el teorema de Hajnal-Szemerédi es seis, lo que se logra dando a cada vértice un color distinto.
Otro fenómeno interesante lo exhibe un gráfico bipartito completo diferente, K 2 n + 1,2 n + 1 . Este gráfico tiene una coloración bicolor equitativa, dada por su bipartición. Sin embargo, no tiene una coloración equitativa (2 n + 1): cualquier partición equitativa de los vértices en tantas clases de color tendría que tener exactamente dos vértices por clase, pero los dos lados de la bipartición no pueden dividirse cada uno en pares porque tienen un número impar de vértices. Por tanto, el umbral cromático equitativo de esta gráfica es 2 n + 2, significativamente mayor que su número cromático equitativo de dos.
El teorema de Brooks establece que cualquier gráfico conectado con grado máximo Δ tiene una coloración Δ, con dos excepciones ( gráficos completos y ciclos impares). Sin embargo, esta coloración puede, en general, estar lejos de ser equitativa. Paul Erdős (1964) conjeturó que es posible una coloración equitativa con un solo color más: cualquier gráfico con grado máximo Δ tiene una coloración equitativa con Δ + 1 colores. El caso Δ = 2 es sencillo (cualquier unión de caminos y ciclos puede colorearse equitativamente usando un patrón repetido de tres colores, con pequeños ajustes en la repetición al cerrar un ciclo) y el caso Δ + 1= n /3 ya lo habíamos hecho previamente. ha sido resuelto por Corrádi y Hajnal (1963). La conjetura completa fue probada por Hajnal y Szemerédi (1970) y ahora se conoce como teorema de Hajnal-Szemerédi. Su prueba original fue larga y complicada; Kierstead y Kostochka (2008) dieron una prueba más sencilla. Kierstead y Kostochka describieron un algoritmo de tiempo polinomial para encontrar coloraciones equitativas con tantos colores; le dan crédito a Marcelo Mydlarz y Endre Szemerédi por un algoritmo de tiempo polinomial inédito. Kierstead y Kostochka también anuncian, pero no prueban, un fortalecimiento del teorema, para demostrar que existe una coloración k+1 equitativa siempre que cada dos vértices adyacentes tengan grados que sumen como máximo 2 k + 1.
Meyer (1973) conjeturó una forma del teorema de Brooks para la coloración equitativa: cada gráfico conectado con grado máximo Δ tiene una coloración equitativa con Δ o menos colores, con las excepciones de gráficos completos y ciclos impares. Una versión reforzada de la conjetura establece que cada gráfico tiene una coloración equitativa con exactamente Δ colores, con una excepción adicional, un gráfico bipartito completo en el que ambos lados de la bipartición tienen el mismo número impar de vértices. [1]
Seymour (1974) propuso un fortalecimiento del teorema de Hajnal-Szemerédi que también incluye el teorema de Dirac de que los grafos densos son hamiltonianos : conjeturó que, si cada vértice en un grafo de n -vértices tiene al menos kn /( k + 1) vecinos , entonces el gráfico contiene como subgrafo el gráfico formado conectando vértices que están como máximo k pasos separados en un n -ciclo. El caso k = 1 es el propio teorema de Dirac. El teorema de Hajnal-Szemerédi se puede recuperar de esta conjetura aplicando la conjetura para valores mayores de k al gráfico complementario de un gráfico dado y utilizando como clases de color subsecuencias contiguas de vértices del n -ciclo. La conjetura de Seymour ha sido probada aproximadamente, es decir, para gráficos donde cada vértice tiene al menos kn /( k + 1)+o( n ) vecinos. [4] La prueba utiliza varias herramientas profundas, incluido el propio teorema de Hajnal-Szemerédi.
Otra generalización más del teorema de Hajnal-Szemerédi es la conjetura de Bollobás-Eldridge-Catlin (o conjetura BEC para abreviar). [5] Esto establece que si G 1 y G 2 son gráficos sobre n vértices con grado máximo Δ 1 y Δ 2 respectivamente, y si (Δ 1 + 1)(Δ 2 + 1) ≤ n+1 , entonces G 1 y G 2 se puede empaquetar. Es decir, G 1 y G 2 se pueden representar en el mismo conjunto de n vértices sin aristas en común. El teorema de Hajnal-Szemerédi es el caso especial de esta conjetura en el que G 2 es una unión disjunta de camarillas . Catlin (1974) proporciona una condición similar pero más fuerte sobre Δ 1 y Δ 2 bajo la cual se puede garantizar la existencia de dicho empaquetamiento.
Para cualquier árbol con grado máximo Δ, el número cromático equitativo es como máximo
y el peor de los casos ocurre para una estrella. Sin embargo, la mayoría de los árboles tienen un número cromático equitativo significativamente menor: si un árbol con n vértices tiene Δ ≤ n /3 − O(1), entonces tiene una coloración equitativa con solo tres colores. [7] Furmańczyk (2006) estudia el número cromático equitativo de productos gráficos .
También se ha estudiado el problema de encontrar coloraciones equitativas con el menor número posible de colores (por debajo del límite Hajnal-Szemerédi). Se puede probar una reducción sencilla de la coloración del gráfico a la coloración equitativa agregando suficientes vértices aislados a un gráfico, lo que demuestra que es NP-completo probar si un gráfico tiene una coloración equitativa con un número determinado de colores (mayor que dos). Sin embargo, el problema se vuelve más interesante cuando se restringe a clases especiales de gráficos o desde el punto de vista de la complejidad parametrizada . Bodlaender y Fomin (2005) demostraron que, dado un gráfico G y un número c de colores, es posible probar si G admite una coloración c equitativa en el tiempo O( n O( t ) ), donde t es el ancho del árbol de GRAMO ; en particular, la coloración equitativa se puede resolver de manera óptima en tiempo polinomial para árboles (anteriormente conocido por Chen y Lih 1994) y gráficos planos externos . También se conoce un algoritmo de tiempo polinomial para colorear equitativamente gráficos divididos . [8] Sin embargo, Fellows et al. (2007) demuestran 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 independiente de este parámetro, o incluso que la dependencia del parámetro pueda eliminarse del exponente en la fórmula para el tiempo de ejecución.
Una motivación para la coloración equitativa sugerida por Meyer (1973) tiene que ver con los problemas de programación . En esta aplicación, los vértices de un gráfico representan una colección de tareas a realizar y un borde conecta dos tareas que no deben realizarse al mismo tiempo. El color de este gráfico representa una partición de las tareas en subconjuntos que pueden realizarse simultáneamente; por lo tanto, la cantidad de colores en la coloración corresponde a la cantidad de pasos de tiempo necesarios para realizar toda la tarea. Debido a consideraciones de equilibrio de carga , es deseable realizar un número igual o casi igual de tareas en cada paso de tiempo, y este equilibrio es exactamente lo que logra una coloración equitativa. Furmańczyk (2006) menciona una aplicación específica de este tipo de problema de programación, asignando cursos universitarios a franjas horarias de una manera que distribuya los cursos uniformemente entre las franjas horarias disponibles y evite programar pares de cursos incompatibles al mismo tiempo entre sí.
El teorema de Hajnal-Szemerédi también se ha utilizado para limitar la varianza de sumas de variables aleatorias con dependencia limitada (Pemmaraju 2001; Janson y Ruciński 2002). Si (como en la configuración del lema local de Lovász ) cada variable depende como máximo de Δ otras, se puede utilizar una coloración equitativa 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 da como resultado resultados generales más estrictos. límites a la variación que si la partición se realizara de manera no equitativa.
