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 diferentes colores es lo más uniforme posible. Por ejemplo, dar a cada vértice un color distinto sería equitativo, pero normalmente se utilizarían muchos más colores de los necesarios en una coloración equitativa óptima. Una forma equivalente de definir una coloración equitativa es que es una incrustación del grafo dado como un subgrafo de un grafo 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 grafo G es el número k más pequeño tal que G tiene una coloración equitativa con k colores. Pero G podría no tener coloraciones equitativas para algunos números mayores 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 grafo con grado máximo Δ tiene una coloración equitativa con Δ + 1 colores. Varias conjeturas relacionadas permanecen abiertas. Los algoritmos de tiempo polinomial también son conocidos por encontrar una coloración que coincida con este límite, [3] y para encontrar coloraciones óptimas de clases especiales de grafos, pero el problema más general de decidir si un grafo arbitrario tiene una coloración equitativa con un número dado de colores es NP-completo .
La estrella K 1,5 (un único vértice central conectado a otros cinco) es un grafo bipartito completo y, por lo tanto, puede colorearse 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 grafo es cuatro: 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 para garantizar que las otras clases de color tengan como máximo dos vértices.
En términos más generales, Meyer (1973) observa que cualquier estrella K 1, n necesita colores en cualquier coloración equitativa; por lo tanto, el número cromático de un grafo puede diferir de su número de coloración equitativa 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 al darle a cada vértice un color distinto.
Otro fenómeno interesante lo muestra un grafo bipartito completo diferente, K 2 n + 1,2 n + 1 . Este grafo tiene una coloración 2 equitativa, dada por su bipartición. Sin embargo, no tiene una coloración (2 n + 1) equitativa: cualquier partición equitativa de los vértices en esa cantidad de clases de color tendría que tener exactamente dos vértices por clase, pero los dos lados de la bipartición no pueden dividirse en pares porque tienen un número impar de vértices. Por lo tanto, el umbral cromático equitativo de este grafo es 2 n + 2, significativamente mayor que su número cromático equitativo de dos.
El teorema de Brooks establece que cualquier grafo conexo con grado máximo Δ tiene una coloración Δ, con dos excepciones ( grafos completos y ciclos impares). Sin embargo, esta coloración puede, en general, estar lejos de ser equitativa. Paul Erdős (1964) conjeturó que una coloración equitativa es posible con solo un color más: cualquier grafo 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 utilizando 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 había sido resuelto previamente por Corrádi y Hajnal (1963). La conjetura completa fue demostrada por Hajnal y Szemerédi (1970), y ahora se conoce como el teorema de Hajnal-Szemerédi. Su prueba original fue larga y complicada; Kierstead y Kostochka (2008) dieron una prueba más simple. Kierstead y Kostochka describieron un algoritmo de tiempo polinómico para encontrar coloraciones equitativas con esta cantidad de colores; atribuyen a Marcelo Mydlarz y Endre Szemerédi un algoritmo de tiempo polinómico no publicado anteriormente. Kierstead y Kostochka también anuncian, pero no prueban, un fortalecimiento del teorema, para mostrar 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 grafo conexo con grado máximo Δ tiene una coloración equitativa con Δ o menos colores, con las excepciones de los grafos completos y los ciclos impares. Una versión reforzada de la conjetura establece que cada uno de esos grafos tiene una coloración equitativa con exactamente Δ colores, con una excepción adicional, un grafo 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 subsume 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 grafo contiene como subgrafo el grafo formado al conectar vértices que están a lo sumo k pasos de distancia en un n -ciclo. El caso k = 1 es el teorema de Dirac en sí mismo. El teorema de Hajnal-Szemerédi puede recuperarse de esta conjetura aplicando la conjetura para valores mayores de k al grafo complementario de un grafo dado, y usando como clases de color subsecuencias contiguas de vértices del n -ciclo. La conjetura de Seymour ha sido aproximadamente probada, es decir, para grafos 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 del teorema de Hajnal-Szemerédi es la conjetura de Bollobás-Eldridge-Catlin (o conjetura BEC para abreviar). [5] Esta establece que si G 1 y G 2 son grafos en 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 pueden empaquetarse. Es decir, G 1 y G 2 pueden representarse 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 en Δ 1 y Δ 2 bajo la cual se puede garantizar que existe tal empaquetamiento.
Para cualquier árbol con grado máximo Δ, el número cromático equitativo es como máximo
con el peor caso ocurriendo 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 la menor cantidad posible de colores (por debajo del límite de Hajnal-Szemerédi). Se puede demostrar una reducción directa de la coloración de grafos a la coloración equitativa añadiendo suficientes vértices aislados a un grafo, lo que demuestra que es NP-completo probar si un grafo tiene una coloración equitativa con un número dado de colores (mayor que dos). Sin embargo, el problema se vuelve más interesante cuando se restringe a clases especiales de grafos o desde el punto de vista de la complejidad parametrizada . Bodlaender y Fomin (2005) demostraron que, dado un grafo G y un número c de colores, es posible probar si G admite una c -coloración equitativa en tiempo O( n O( t ) ), donde t es el ancho del árbol de G ; en particular, la coloración equitativa se puede resolver de forma óptima en tiempo polinomial para árboles (previamente conocido debido a Chen y Lih 1994) y grafos planos exteriores . También se conoce un algoritmo de tiempo polinomial para la coloración equitativa de 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]-duro. 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 trasladarse fuera del exponente en la fórmula para el tiempo de ejecución.
Una de las motivaciones para la coloración equitativa sugerida por Meyer (1973) se refiere a los problemas de programación . En esta aplicación, los vértices de un gráfico representan una colección de tareas que se deben realizar, y una arista conecta dos tareas que no se deben realizar al mismo tiempo. Una coloración de este gráfico representa una partición de las tareas en subconjuntos que se pueden realizar simultáneamente; por lo tanto, la cantidad de colores en la coloración corresponde a la cantidad de pasos de tiempo necesarios para realizar la tarea completa. Debido a consideraciones de equilibrio de carga , es deseable realizar cantidades iguales o casi iguales 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 de manera uniforme entre las franjas horarias disponibles y evite programar pares de cursos incompatibles al mismo tiempo.
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 & Ruciński 2002). Si (como en la configuración para el lema local de Lovász ) cada variable depende de, como máximo, Δ 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 límites generales más estrictos en la varianza que si la partición se realizara de manera no equitativa.
