Triángulo monocromático

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énEditar

ReferenciasEditar