Función de Tardos
From Wikipedia, the free encyclopedia
En teoría de grafos y en complejidad de circuitos, la función de Tardos es un invariante de un grafo introducido por Éva Tardos en 1988.[1][2]
La función de Tardos posee las siguientes propiedades:[1]
- Al igual que el número de Lovász del complemento de un grafo, la función de Tardos se encuentra entre el número de clique y el número cromático del grafo. Ambos números son NP-difíciles de calcular.
- La función de Tardos es monótona, en el sentido de que añadir aristas a un grafo solo puede hacer que su función de Tardos aumente o se mantenga constante, pero nunca disminuya.
- La función de Tardos se puede calcular en tiempo polinómico.
- Cualquier circuito monótono para calcular la función de Tardos requiere un tamaño exponencial.
