En teoría de grafos y en informática teórica , el problema del triángulo monocromático es un problema algorítmico sobre grafos, en el que el objetivo es dividir los bordes de un grafo dado en dos subgrafos sin triángulos . Es un problema NP-completo pero manejable con parámetros fijos en grafos con un ancho de árbol acotado .
El problema del triángulo monocromático toma como entrada un grafo no dirigido de n nodos G(V,E) con un conjunto de nodos V y un conjunto de aristas E. La salida es un valor booleano, verdadero si el conjunto de aristas E de G se puede dividir en dos conjuntos disjuntos E1 y E2, de modo que ambos subgrafos G1(V,E1) y G2(V,E2) son grafos sin triángulos , y falso en caso contrario. Este problema de decisión es NP-completo . [1]
El problema puede generalizarse a la coloración de aristas sin triángulos , encontrando una asignación de colores a las aristas de un grafo de modo que ningún triángulo tenga las tres aristas del mismo color. El problema del triángulo monocromático es el caso especial de la coloración de aristas sin triángulos cuando hay exactamente dos colores disponibles. Si existe una coloración de aristas sin triángulos de dos colores, entonces las aristas de cada color forman los dos conjuntos E1 y E2 del problema del triángulo monocromático. Por el contrario, si el problema del triángulo monocromático tiene una solución, podemos usar un color para E1 y un segundo color para E2 para obtener una coloración de aristas sin triángulos.
Por el teorema de Ramsey , para cualquier número finito k de colores, existe un número n tal que los grafos completos de n o más vértices no tienen aristas con colores k sin triángulos . Para k = 2, el valor correspondiente de n es 6. Es decir, la respuesta al problema del triángulo monocromático en el grafo completo K 6 es no.
Es sencillo expresar el problema del triángulo monocromático en la lógica monádica de segundo orden de grafos (MSO 2 ), mediante una fórmula lógica que afirma la existencia de una partición de las aristas en dos subconjuntos tales que no existen tres vértices mutuamente adyacentes cuyas aristas pertenecen todas al mismo lado de la partición. Del teorema de Courcelle se deduce que el problema del triángulo monocromático es tratable con parámetros fijos en grafos de ancho de árbol acotado . Más precisamente, existe un algoritmo para resolver el problema cuyo tiempo de ejecución es el número de vértices del grafo de entrada multiplicado por una función de rápido crecimiento pero computable del ancho del árbol. [2]