Cambiar a contenido. | Saltar a navegación

Herramientas Personales
Entrar

Navegación

Usted está aquí: Inicio / Actividades / Seminarios / Seminario de Combinatoria, Geometría y Convexos / Actividades del Seminario de Combinatoria, Geometría y Convexos / ¿Cuál es la complejidad de decidir si el número dicromático de una digráfica es 2? / Miguel Angel Pizaña.

¿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.
Ponente:
Cuándo 06/05/2008
de 17:00 a 18:00
Dónde Graciela Salicrup
Agregar evento al calendario vCal
iCal