RT info:eu-repo/semantics/bachelorThesis
T1 Coloración de Grafos
A1 Oval Trujillo, Zulema
K1 Coloración
K1 Grafo planar
K1 Teorema Combinatorio de los ceros
AB El objetivo principal de este trabajo es el estudio del problema de lacoloraci´on de grafos haciendo uso de herramientas combinatorias yalgebraicas. Comenzamos por la obtenci´on de cotas superiores e inferiores del n´umero crom´atico de un grafo y aportando algoritmos decoloraci´on (no necesariamente ´optima) de grafos. Tras esto, estudiamos la coloraci´on de grafos planares y demostramos varias versionesd´ebiles del Teorema de los cuatro colores, el cual establece que ungrafo planar es 4-coloreable. Por ´ultimo caracterizamos la propiedadde que un grafo sea k-coloreable en t´erminos de la pertenencia de uncierto polinomio a un ideal. De este resultado deducimos un algoritmo que determina el n´umero crom´atico de un grafo. Incluimos unaimplementaci´on en singular del algoritmo propuesto.
YR 2021
FD 2021
LK http://riull.ull.es/xmlui/handle/915/24111
UL http://riull.ull.es/xmlui/handle/915/24111
LA es
DS Repositorio institucional de la Universidad de La Laguna
RD 26-dic-2024