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 gráfico 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 los siguientes:
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 gráfico 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 gráfico plano se puede descomponer 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 adecuada de un gráfico cordal es también una coloración acíclica. Dado que los gráficos cordales se pueden colorear de manera óptima en tiempo O ( n + m ), lo mismo ocurre con la coloración acíclica en esa clase de gráficos.
Skulrattanakulchai (2004) proporcionó un algoritmo de tiempo lineal para colorear acíclicamente un gráfico de grado máximo ≤ 3 usando 4 colores o menos.
Borodin, OV (1979), "Sobre coloraciones acíclicas de gráficos planos", Matemáticas discretas , 25 (3): 211–236, doi : 10.1016/0012-365X(79)90077-3.
Burstein, MI (1979), "Cada gráfico tetravalente tiene una coloración acíclica de cinco colores (en ruso)", Soobšč. Akád. Nauk Gruzin. RSS , 93 : 21-24.
Coleman, Thomas F .; Cai, Jin-Yi (1986), "El problema de la coloración cíclica y la estimación de matrices hessianas dispersas" (PDF) , Revista SIAM sobre métodos algebraicos y discretos , 7 (2): 221–235, doi :10.1137/0607026, hdl : 1813/6485.
Fertín, Guillaume; Raspaud, André (2008), "Coloración acíclica de gráficos 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), "Computación eficiente de arpilleras dispersas 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 CS1: falta el editor de la ubicación ( enlace ).
Kostochka, Alexandr V.; Stocker, Christopher (2011), "Los gráficos con grado máximo 5 se pueden colorear acíclicamente con 7 colores", 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", Cartas de procesamiento de información , 92 (4): 161–167, doi :10.1016/j.ipl.2004.08.002.
Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "Coloración de vértices acíclicos de gráficos de máximo grado seis", LAGOS'09 – Quinto Simposio Latinoamericano de Algoritmos, Gráficos y Optimización , Apuntes Electrónicos en Matemática Discreta, vol. 35, Elsevier, págs. 177–182, doi :10.1016/j.endm.2009.11.030, SEÑOR 2579427
enlaces externos
Coloraciones de estrellas y coloraciones acíclicas (1973), presente en Research Experiences for Graduate Students (REGS) de la Universidad de Illinois, 2008.
Coloración acíclica de gráficos de grado máximo ∆, diapositivas de charla presentadas por G. Fertin y A. Raspaud en EUROCOMB 05, Berlín, 2005.
