Coloración de gráficos acíclicos
En la teoría de grafos, una coloración acíclica es una coloración de vértice (adecuada) en la que cualquier subgráfico de dos colores no tiene ciclos .
El número cromático acíclico A( G ) de un gráfico G es el menor número de colores necesarios en cualquier coloración acíclica G .
La coloración acíclica a menudo se asocia con gráficos en superficies no planas.
Límites superiores
A( G ) ≤ 2 si y solo si G no tiene ciclos.
Los límites de A( G ) en términos del grado máximo Δ( G ) del gráfico G incluyen lo siguiente:
- A( G ) ≤ 4 si Δ( G ) = 3. (Grünbaum 1973)
- A( G ) ≤ 5 si Δ( G ) = 4. (Burstein 1979)
- A( G ) ≤ 8 si Δ( G ) = 5.( Yadav, Satish 2008 )
- A( G ) ≤ 12 si Δ( G ) = 6.( Yadav, Satish 2009 )
Un hito en el estudio de la coloración acíclica es la siguiente respuesta positiva a la conjetura de Grünbaum:
Teorema. (Borodín 1979)
A( G ) ≤ 5 si G es plano.
Grünbaum (1973) introdujo una coloración acíclica y un número cromático acíclico e hizo una conjetura, que fue probada por Borodin. Borodin tardó varios años de verificación diligente de 450 configuraciones para demostrarlo. Una consecuencia de este teorema es que cualquier gráfico plano se puede descomponer en un conjunto independiente y dos bosques . (Stein 1970, 1971)
Algoritmos y complejidad
El problema de determinar si A( G ) ≤ 3 se cumple es NP-completo (Kostochka 1978). Coleman y Cai ( Coleman, Cai 1986 ) demostraron que el problema sigue siendo NP-completo incluso para grafos bipartitos.
Gebremedhin y otros ( Gebremedhin, Tarafdar, Pothen, Walther 2008 ) demostraron que cualquier coloración adecuada de los vértices de un grafo cordal es una coloración acíclica. Dado que es posible encontrar una coloración óptima para grafos cordales en tiempo O(n+m) , lo mismo es cierto para una coloración acíclica en esta clase de grafos.
Skulrattanakulchai ( Skulrattanakulchai 2004 ) presenta un algoritmo lineal en el tiempo para la coloración acíclica de un gráfico de grado máximo ≤ 3 en 4 colores o menos . Yadav y Satish ( Yadav, Satish 2008 ) describen un algoritmo de coloreado de gráficos acíclicos lineales en el tiempo con un grado máximo ≤ 5 usando 8 colores o menos, así como un algoritmo para colorear un gráfico con un grado máximo ≤ 6 usando 12 colores o menos.
Véase también
Notas
Enlaces
- MI Burstein. Cada gráfico de 4 valentes tiene un color acíclico de 5 (en ruso) // Soobšč. Akád. Nauk Gruzin. SSR. - 1979. - T. 93 . — P. 21–24 .
- B. Grünbaum. Coloraciones acíclicas de grafos planos // Israel J. Math .. - 1973. - T. 14 . — S. 390–408 . -doi : 10.1007/ BF02764716 .
- Thomas F. Coleman, Jin-Yi Cai. El problema de la coloración cíclica y la estimación de matrices hessianas dispersas // SIAM. J. sobre métodos algebraicos y discretos. - 1986. - T. 7 . — S. 221–235 . -doi : 10.1137/ 0607026 . .
- Guillaume Fertin, André Raspaud. Coloración acíclica de gráficos de máximo grado cinco: Nueve colores son suficientes // Letras de procesamiento de información. - 2008. - T. 105 . — S. 65–72 . -doi : 10.1016/ j.ipl.2007.08.022 . .
- Kishore Yadav, Venkaiah Satish. Coloración acíclica de gráficos de máximo grado cinco: Ocho colores son suficientes // ICGTA. - 2008. - T. nulo . - C. cero . .
- Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli. Coloración acíclica de gráficas de máximo grado seis: Doce colores son suficientes // Notas Electrónicas en Matemática Discreta. - 2009. - T. 35 . — S. 177–182 . -doi : 10.1016/ j.endm.2009.11.030 . .
- Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, Andrea Walther. Cálculo eficiente de hessianas dispersas mediante coloración y diferenciación automática // Informa Journal on Computing. - 2008. - T. 21 . - S. 209 . -doi : 10.1287/ ijoc.1080.0286 . .
- Jensen, Tommy R.; Toft, Bjarne (1995). Problemas de coloreado de gráficas . Nueva York: Wiley-Interscience. ISBN 0-471-02865-7 .
- Kostochka, AV (1978). Límites superiores de funciones cromáticas de gráficos (en ruso). Tesis doctoral, Novosibirsk.
- San Skulrattanakulchai. Coloraciones acíclicas de gráficos subcúbicos // Cartas de procesamiento de información. - 2004. - T. 92 . — S. 161–167 . -doi : 10.1016/ j.ipl.2004.08.002 . .
- SK Stein. Conjuntos B y problemas de coloración // Bull. amer Matemáticas. Soc.. - 1970. - T. 76 . — S. 805–806 . -doi : 10.1090 / S0002-9904-1970-12559-9 .
- SK Stein. Conjuntos B y mapas planos // Pacific J. Math .. - 1971. - T. 37 . — S. 217–224 .
Enlaces externos