En teoría de grafos e informática teórica , el problema del triángulo monocromático es un problema algorítmico en gráficos, en el que el objetivo es dividir los bordes de un gráfico determinado en dos subgrafos libres de triángulos . Es NP completo pero manejable con parámetros fijos en gráficos de ancho de árbol acotado .
El problema del triángulo monocromático toma como entrada un gráfico 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 los dos subgrafos G1(V,E1) y G2(V,E2) son gráficos sin triángulos y falsos en caso contrario. Este problema de decisión es NP-completo . [1]
El problema se puede generalizar a la coloración de aristas sin triángulos , encontrando una asignación de colores a las aristas de un gráfico 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 coloración de bordes sin triángulos cuando hay exactamente dos colores disponibles. Si existe una coloración de bordes sin triángulos de dos colores, entonces los bordes 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 solución, podemos usar un color para E1 y un segundo color para E2 para obtener una coloración de bordes sin triángulo.
Según el teorema de Ramsey , para cualquier número finito k de colores, existe un número n tal que las gráficas completas de n o más vértices no tienen coloraciones de bordes libres de triángulos con k colores. Para k = 2, el valor correspondiente de n es 6. Es decir, la respuesta al problema del triángulo monocromático en el gráfico completo K 6 es no.
Es sencillo expresar el problema del triángulo monocromático en la lógica monádica de grafos de segundo orden (MSO 2 ), mediante una fórmula lógica que afirma la existencia de una partición de las aristas en dos subconjuntos de modo que no existan tres vértices mutuamente adyacentes. cuyos bordes pertenecen todos al mismo lado de la partición. Del teorema de Courcelle se deduce que el problema del triángulo monocromático es manejable con parámetros fijos en gráficas 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 gráfico de entrada multiplicado por una función computable pero de rápido crecimiento del ancho del árbol. [2]