Permítanme ampliar mi comentario. Supongamos que tenemos algún algoritmo polinómico 3COL que devuelve una coloración 3 válida 3COL (G) de cualquier gráfico libre de triángulos de 3 colores $G$ en tiempo polinómico.
Como 3COL es polinómico hay algunos $a,b,c \in \mathbb{N}$ , tal que en un gráfico con $n$ vértices, 3COL siempre se termine después de $a n^b+c$ instrucciones.
Afirmo que existe un algoritmo polinómico para decidir si un grafo sin triángulos dado es tricolable (en particular, decidirá si el grafo no es tricolable):
- Dejemos que $G$ sea cualquier gráfico libre de triángulos en $n$ vértices.
- Ejecutamos $a n^b+c+1$ instrucciones de 3COL (G). Si el algoritmo no termina $G$ no tiene 3 colores.
- Supongamos que el algoritmo termina con alguna coloración. O es válido (entonces hemos terminado y el grafo es tricolor) o no es válido. Si es inválido, sabemos que el grafo no puede ser tricolor como 3COL es correcta en los grafos libres de triángulos de 3 colores.
Este algoritmo se ejecuta en tiempo polinómico y decide el $NP$ -problema incompleto si un grafo sin triángulos es 3 veces coloreable, por lo que no puede existir a menos que $P=NP$ .
No había visto este tipo de argumento antes, así que dime si ves alguna laguna en mi prueba.
