El problema del triángulo monocromático es un problema de decisión que pertenece a la clase de los problemas NP-completos.
Entrada: Un grafo no dirigido G(V,E), donde V es un conjunto de n vértices y E es el conjunto de aristas.
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 Teorema de Ramsey
Referencias . A1.1: GT6, pg.191.θ
Categoría:Problemas NP-completos