¿Cuál es la complejidad de decidir si el número dicromático de una digráfica es 2? / Miguel Angel Pizaña.

En 1985 Vi­ctor 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.