Ir al contenido

Triángulo monocromático

De Wikipedia, la enciclopedia libre

El problema del triángulo monocromático es un problema de decisión que pertenece a la clase de los problemas NP-completos.

  • Pregunta: ¿Puede el conjunto E ser particionado en dos conjuntos disjuntos E1 y E2, tales que ninguno de los dos grafos G1(V,E1) y G2(V,E2) contengan un triángulo; es decir, tal que para todos los vértices de E1 y E2, no exista un conjunto {u,v,w} tal que las aristas {u,v}, {u,w}, {v,w} estén definidas?

Véase también

[editar]

Referencias

[editar]