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.

• 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?

• Teorema de Ramsey

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5 .. A1.1: GT6, pg.191.θ