En teoría de grafos , una coloración acíclica es una coloración de vértice (adecuada) en la que cada subgrafo bicromático es acíclico . El número cromático acíclico A( G ) de un grafo G es la menor cantidad de colores necesarios en cualquier coloración acíclica de G .
La coloración acíclica a menudo se asocia con gráficos incrustados en superficies no planas.
Límites superiores
A( G ) ≤ 2 si y sólo si G es acíclico.
Los límites de A( G ) en términos de Δ( G ), el grado máximo de G , incluyen lo siguiente:
A( G ) ≤ 4 si Δ( G ) = 3. (Grünbaum 1973)
A( G ) ≤ 5 si Δ( G ) = 4. (Burstein 1979)
A( G ) ≤ 7 si Δ( G ) = 5. (Kostochka y Stocker 2011)
A( G ) ≤ 12 si Δ( G ) = 6. (Varagani et al. 2009)
Un hito en el estudio de la coloración acíclica es la siguiente respuesta afirmativa a una conjetura de Grünbaum:
Teorema (Borodin 1979) A( G ) ≤ 5 si G es un grafo plano.
Grünbaum (1973) introdujo la coloración acíclica y el número cromático acíclico, y conjeturó el resultado en el teorema anterior. La prueba de Borodin implicó varios años de minuciosa inspección de 450 configuraciones reducibles. Una consecuencia de este teorema es que cada grafo plano puede descomponerse en un conjunto independiente y dos bosques inducidos . (Stein 1970, 1971)
Algoritmos y complejidad
Es NP-completo determinar si A( G ) ≤ 3. (Kostochka 1978)
Coleman y Cai (1986) demostraron que la variante de decisión del problema es NP-completa incluso cuando G es un gráfico bipartito .
Gebremedhin et al. (2008) demostraron que cada coloración de vértice apropiada de un grafo cordal es también una coloración acíclica. Dado que los grafos cordales pueden colorearse de manera óptima en tiempo O( n + m ), lo mismo es cierto para la coloración acíclica en esa clase de grafos.
Skulrattanakulchai (2004) presentó un algoritmo de tiempo lineal para colorear acíclicamente un gráfico de grado máximo ≤ 3 utilizando 4 colores o menos.
Coleman, Thomas F.; Cai, Jin-Yi (1986), "El problema de coloración cíclica y la estimación de matrices hessianas dispersas" (PDF) , SIAM Journal on Algebraic and Discrete Methods , 7 (2): 221–235, doi :10.1137/0607026, hdl : 1813/6485.
Fertin, Guillaume; Raspaud, André (2008), "Coloración acíclica de grafos de grado máximo cinco: Nueve colores son suficientes", Information Processing Letters , 105 (2): 65–72, CiteSeerX 10.1.1.78.5369 , doi :10.1016/j.ipl.2007.08.022, S2CID 12886305.
Gebremedhin, Assefaw H.; Tarafdar, Arijit; Pothen, Alex; Walther, Andrea (2008), "Cálculo eficiente de hessianos dispersos mediante coloración y diferenciación automática", INFORMS Journal on Computing , 21 (2): 209–223, doi :10.1287/ijoc.1080.0286.
Jensen, Tommy R.; Toft, Bjarne (1995), Problemas de coloración de gráficos , Nueva York: Wiley-Interscience, ISBN 978-0-471-02865-9.
Kostochka, AV (1978), Límites superiores de funciones cromáticas de gráficos , Tesis doctoral (en ruso), Novosibirsk{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
Kostochka, Alexandr V.; Stocker, Christopher (2011), "Los gráficos con grado máximo 5 son acíclicamente 7-coloreables", Ars Mathematica Contemporanea , 4 (1): 153–164, doi : 10.26493/1855-3974.198.541 , MR 2785823.
Skulrattanakulchai, San (2004), "Coloraciones acíclicas de gráficos subcúbicos", Information Processing Letters , 92 (4): 161–167, doi :10.1016/j.ipl.2004.08.002.
Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "Coloración acíclica de vértices de grafos de grado máximo seis", LAGOS'09 – Quinto Simposio Latinoamericano de Algoritmos, Grafos y Optimización , Electronic Notes in Discrete Mathematics, vol. 35, Elsevier, pp. 177–182, doi :10.1016/j.endm.2009.11.030, MR 2579427
Enlaces externos
Coloraciones estelares y coloraciones acíclicas (1973), presente en Experiencias de Investigación para Estudiantes de Posgrado (REGS) en la Universidad de Illinois, 2008.
Coloración acíclica de gráficos de grado máximo ∆, diapositivas de la charla presentada por G. Fertin y A. Raspaud en EUROCOMB 05, Berlín, 2005.
