Métodos polinomiales para trabajar con grafos

Abstract

La coloración de grafos ha sido un problema recurrente desde hace varios siglos. Aunque existen resultados que acotan el número de colores necesarios para determinados tipos de grafos, en esta memoria se da un resultado general que permite distinguir si un grafo es k-coloreable y únicamente k-coloreable. Es una ilustración de la manera de utilizar los métodos algebraicos para resolver problemas de índole combinatorio. Para ello se utilizarán métodos polinomiales basados en las bases de Gröbner, por lo tanto también se tratarán algunas propiedades de estos objetos algebraicos. Como aplicación, veremos que estos métodos se pueden usar para resolver Sudokus.