Coloración acíclica
En la teoría de grafos , un colorante acíclico es un (adecuado) para colorear vértice en el que cada 2-cromática subgrafo es acíclico . El número acíclico cromática A ( G ) de un gráfico G es los colores menor número necesarias en cualquier coloración acíclico de G .
Un hito en el estudio de la coloración acíclica es la siguiente respuesta afirmativa a una conjetura de Grünbaum:
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 se puede descomponer en un conjunto independiente y dos bosques inducidos . (Stein 1970 , 1971 )
Coleman y Cai (1986) demostraron que la variante de decisión del problema es NP-completo incluso cuando G es un gráfico bipartito.
Gebremedhin y col. (2008) demostraron que toda coloración de vértice adecuada de un grafo cordal es también una coloración acíclica. Dado que los gráficos cordales se pueden colorear de manera óptima en el tiempo O ( n + m ), lo mismo es cierto para 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 utilizando 4 colores o menos .
