En 1985 Victor Neumann-Lara y Jorge Urrutia plantean este problema y
en esta plática probaremos que el problema es NP-Completo. El número
dicromático dc(D) de una digráfica D es el mÃínimo número de colores con los que se puede colorear una digráfica de forma que no se formen ciclos dirigidos monocromáticos. Es fácil ver que el número dicromático es una generalización del número cromático. Por esta vía es fácil mostrar que para cada k>=3, el
problema de decidir si dc(D)=k, es NP-Completo. Pero el caso k=2 permanecé abierto. La prueba de hecho es sorprendentemente simple y elemental, así que
habrá tiempo suficiente para explicar todo con detalle.
Ubicado en
Actividades académicas
/
…
/
Seminario VNL
/
Actividades del Seminario de Combinatoria, Geometría y Convexos
Correo interno