Problemas de coloración de grafos y grafos fuertemente regulares

Abstract

En este trabajo se profundizará en varias cuestiones de Teoría de Grafos. Por una parte, se estudiarán los clásicos problemas de coloración de grafos: coloración de vértices, de aristas y de caras; y se probará que los dos últimos pueden reducirse al primero mediante los conceptos de grafo de línea y de grafo dual. Por tratarse de problemas NP-completos no tienen una solución sencilla, así que los abordaremos desde diferentes enfoques: estudiando algunas familias importantes de grafos, mediante razonamientos algorítmicos, y acotando el número y el índice cromático. Y por otra parte, se estudiarán los grafos fuertemente regulares, una familia de grafos altamente estructurada , que resultan interesantes por las propiedades que se deducen de dicha estructura y que están estrechamente relacionados con la combinatoria y la teoría algebraica de grafos.