En la 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
- No hay dos vértices adyacentes que tengan el mismo color, y
- El número de vértices en dos clases de color difiere como máximo en uno.
Es decir, la partición de vértices entre los diferentes colores es lo más uniforme posible. Por ejemplo, asignar a cada vértice un color distinto sería equitativo, pero normalmente se usarí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 gráfico dado como un subgráfico de un gráfico 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 kcolores. 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 que k . [2]
El teorema de Hajnal-Szemerédi , planteado como una conjetura por Paul Erdős ( 1964 ) y probado por András Hajnal y Endre Szemerédi ( 1970 ), establece que cualquier gráfico con grado máximo Δ tiene una coloración equitativa con colores Δ + 1. Varias conjeturas relacionadas permanecen abiertas. Los algoritmos de tiempo polinómico también son conocidos por encontrar un color que coincida con este límite, [3] y por encontrar colores óptimos de clases especiales de gráficos, pero el problema más general de decidir si un gráfico arbitrario tiene un color equitativo con un número dado de colores es NP-completo .
Ejemplos de
La estrella K 1,5 que se muestra en la ilustración 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 en una clase de color y cinco en otra, por lo que 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 asegurarse de 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 necesitacolores en cualquier coloración equitativa; por lo 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 garantizados por el teorema de Hajnal-Szemerédi es seis, que se logra dando a cada vértice un color distinto.
Otro fenómeno interesante lo muestra un gráfico bipartito completo diferente, K 2 n + 1,2 n + 1 . Este gráfico tiene un color 2 equitativo, dado 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 lo tanto, el umbral cromático equitativo de este gráfico es 2 n + 2, significativamente mayor que su número cromático equitativo de dos.
Teorema de Hajnal-Szemerédi
El teorema de Brooks establece que cualquier gráfico conectado con grado máximo Δ tiene un color Δ, 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 una coloración equitativa es posible con solo un color más: cualquier gráfico con el grado máximo Δ tiene una coloración equitativa con colores Δ + 1. El caso Δ = 2 es sencillo (cualquier unión de trayectorias y ciclos puede colorearse de manera equitativa utilizando un patrón repetido de tres colores, con pequeños ajustes a la repetición al cerrar un ciclo) y el caso Δ + 1 = n / 3 se había realizado previamente. resuelto por Corrádi y Hajnal (1963) . La conjetura completa fue probada por Hajnal y Szemerédi (1970) , y ahora se conoce como el teorema de Hajnal-Szemerédi. Su prueba original era larga y complicada; Kierstead y Kostochka (2008) dieron una prueba más simple . Kierstead y Kostochka describieron un algoritmo de tiempo polinomial para encontrar coloraciones equitativas con tantos colores; atribuyen a Marcelo Mydlarz y Endre Szemerédi un algoritmo de tiempo polinomial inédito. Kierstead y Kostochka también anuncian, pero no prueban, un fortalecimiento del teorema, para mostrar que existe una coloración k equitativa siempre que cada dos vértices adyacentes tienen grados que suman 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 la excepción 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 subsume el teorema de Dirac de que los gráficos densos son hamiltonianos : conjeturó que, si cada vértice en un gráfico de n -vértices tiene al menos kn / ( k + 1) vecinos , entonces el gráfico contiene como subgráfico el gráfico formado al conectar vértices que están separados como máximo a k pasos en un ciclo n . El caso k = 1 es el propio teorema de Dirac. El teorema de Hajnal-Szemerédi puede recuperarse de esta conjetura aplicando la conjetura para valores mayores de k al gráfico de complemento de un gráfico dado, y usando como clases de color subsecuencias contiguas de vértices del ciclo n . 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 demostración utiliza varias herramientas profundas, incluido el propio teorema de Hajnal-Szemerédi.
Sin embargo, otra generalización 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 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 se puede envasar. 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 la 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 la existencia de tal empaquetamiento.
Clases especiales de gráficos
Para cualquier árbol con el grado máximo Δ, el número cromático equitativo es como máximo
con el peor de los casos 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 .
Complejidad computacional
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 directa de la coloración de la gráfica a la coloración equitativa agregando suficientes vértices aislados a una gráfica, lo que demuestra que es NP-completo probar si una gráfica 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 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 G ; en particular, la coloración equitativa puede resolverse de manera óptima en tiempo polinomial para árboles (previamente conocido debido a Chen & Lih 1994 ) y gráficos de planos exteriores . También se conoce un algoritmo de tiempo polinómico por la coloración equitativa de los 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] -hard. 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 moverse fuera del exponente en la fórmula para el tiempo de ejecución.
Aplicaciones
Una motivación 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 a realizar y un borde conecta dos tareas que no deben realizarse al mismo tiempo. Un color de este gráfico representa una partición de las tareas en subconjuntos que se pueden realizar simultáneamente; por tanto, el número de colores en la coloración corresponde al número de pasos de tiempo necesarios para realizar la tarea completa. 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 manera que los cursos se distribuyan 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 acotar la varianza de las 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 usar 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 resulta en un conjunto más ajustado límites en la varianza que si la partición se realizara de manera no equitativa.
Notas
- ↑ a b Furmańczyk (2006) .
- ^ Tenga en cuenta que, cuando k es mayor que el número de vértices en el gráfico, existe sin embargo una coloración equitativa con k colores en la que todas las clases de color tienen cero o un vértice, por lo que cada gráfico tiene un umbral cromático equitativo.
- ^ Kierstead, Henry A .; Kostochka, Alexandr V .; Mydlarz, Marcelo; Szemerédi, Endre (17 de septiembre de 2010). "Un algoritmo rápido para colorear equitativamente". Combinatorica . 30 (2): 217–224. CiteSeerX 10.1.1.224.5588 . doi : 10.1007 / s00493-010-2483-5 . ISSN 0209-9683 .
- ^ Komlós, Sárközy y Szemerédi (1998) .
- ^ Bollobás y Eldridge (1978) .
- ^ Meyer (1973) .
- ^ Bodlaender y Guy (1983) .
- ^ Chen, Ko y Lih (1996) .
Referencias
- Bodlaender, Hans L .; Fomin, Fedor V. (2005), "Coloreaciones equitativas de gráficos de ancho de árbol acotado", Informática teórica , 349 (1): 22-30, doi : 10.1016 / j.tcs.2005.09.027 , MR 2183465.
- Bollobás, B .; Eldridge, SE (1978), "Paquetes de gráficos y aplicaciones a la complejidad computacional", Journal of Combinatorial Theory , Serie B, 25 (2): 105-124, doi : 10.1016 / 0097-3165 (78) 90073-0 , MR 0511983.
- Bollobás, Béla ; Guy, Richard K. (1983), "Coloración equitativa y proporcional de los árboles", Journal of Combinatorial Theory , Serie B, 34 (2): 177–186, doi : 10.1016 / 0095-8956 (83) 90017-5 , MR 0703602.
- Catlin, Paul A. (1974), "Subgrafos de gráficos. I.", Matemáticas discretas. , 10 (2): 225–233, doi : 10.1016 / 0012-365X (74) 90119-8 , MR 0357230
- Chen, Bor-Liang; Lih, Ko-Wei (1994), "Coloración equitativa de los árboles", Journal of Combinatorial Theory , Serie B, 61 (1): 83–87, doi : 10.1006 / jctb.1994.1032 , MR 1275266.
- Chen, Bor-Liang; Ko, Ming-Tat; Lih, Ko-Wei (1996), " Coloración equitativa y limitada por m de gráficos divididos", Combinatoria y Ciencias de la Computación (Brest, 1995) , Lecture Notes in Computer Science, 1120 , Berlín: Springer-Verlag, págs. 1-5 , doi : 10.1007 / 3-540-61576-8_67 , ISBN 978-3-540-61576-7, Señor 1448914
- Corrádi, K .; Hajnal, A. (1963), "Sobre el número máximo de circuitos independientes en un gráfico", Acta Mathematica Academiae Scientiarum Hungaricae , 14 (3–4): 423–439, doi : 10.1007 / BF01895727 , MR 0200185.
- Erdős, Paul (1964), "Problema 9", en Fieldler, M. (ed.), Teoría de los gráficos y sus aplicaciones , Praga: Academia Checa. Sci. Publ., Pág. 159.
- Compañeros, Michael ; Fomin, Fedor V .; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan ; Thomassen, Carsten (2007), "Sobre la complejidad de algunos problemas coloridos parametrizados por el ancho de árbol", Optimización combinatoria y aplicaciones (PDF) , Lecture Notes in Computer Science, 4616 , Berlín: Springer-Verlag, págs. 366-377, doi : 10.1007 / 978-3-540-73556-4_38 , ISBN 978-3-540-73555-7, Señor 2397574.
- Furmańczyk, Hanna (2006), "Coloración equitativa de los productos gráficos" (PDF) , Opuscula Mathematica , 26 (1): 31–44, MR 2272280.
- Hajnal, A .; Szemerédi, E. (1970), "Prueba de una conjetura de P. Erdős", Teoría combinatoria y sus aplicaciones, II (Proc. Colloq., Balatonfüred, 1969) , Holanda del Norte, págs. 601–623, MR 0297607.
- Janson, Svante ; Ruciński, Andrzej (2002), "La infame cola superior", Estructuras y algoritmos aleatorios , 20 (3): 317–342, doi : 10.1002 / rsa.10031 , MR 1900611.
- Kierstead, HA; Kostochka, AV (2008), "Una breve demostración del teorema de Hajnal-Szemerédi sobre coloración equitativa", Combinatoria, probabilidad y computación , 17 (2): 265-270, doi : 10.1017 / S0963548307008619 , MR 2396352
- Komlós, János ; Sárközy, Gábor N .; Szemerédi, Endre (1998), "Prueba de la conjetura de Seymour para gráficos grandes", Annals of Combinatorics , 2 (1): 43–60, CiteSeerX 10.1.1.122.2352 , doi : 10.1007 / BF01626028 , MR 1682919.
- Meyer, Walter (1973), "Coloración equitativa", American Mathematical Monthly , 80 (8): 920–922, doi : 10.2307 / 2319405 , JSTOR 2319405.
- Pemmaraju, Sriram V. (2001), "Los colores equitativos extienden los límites de Chernoff-Hoeffding", Proc. 12 ° ACM-SIAM Symp. Algoritmos discretos (SODA 2001) , Soda '01, págs. 924–925, ISBN 9780898714906.
- Seymour, P. (1974), "Sección de problemas", en McDonough, TP; Mavron, Eds., VC (eds.), Combinatorics: Proceedings of the British Combinatorial Conference 1973 , Cambridge, Reino Unido: Cambridge Univ. Prensa, págs. 201–202.
enlaces externos
- ECOPT Un algoritmo de bifurcación y corte para resolver el problema de coloración equitativa