En esta charla vamos a estudiar aproximaciones para parámetros de grafos basadas en optimización semidefinida y sumas de cuadrados de polinomios. En la primera parte de la charla repasaremos algunos problemas clásicos en Teoría de Grafos. En particular, consideramos el problema del Numero de Estabilidad (o Independencia) y el problema del Número Cromático, y mostramos aproximaciones basadas en Optimización Semidefinida. En la segunda parte de la charla presentaremos métodos de aproximación para el Número de Estabilidad de un Grafo basados en sumas de cuadrados polinomios. Adicionalmente mostramos algunos resultados recientes sobre este problema que interesectan Teoría de Grafos, Optimización, Geometría Algebraica y Teoría de Complejidad.