Coloración de Grafos

Abstract

El objetivo principal de este trabajo es el estudio del problema de la coloraci´on de grafos haciendo uso de herramientas combinatorias y algebraicas. Comenzamos por la obtenci´on de cotas superiores e inferiores del n´umero crom´atico de un grafo y aportando algoritmos de coloraci´on (no necesariamente ´optima) de grafos. Tras esto, estudiamos la coloraci´on de grafos planares y demostramos varias versiones d´ebiles del Teorema de los cuatro colores, el cual establece que un grafo planar es 4-coloreable. Por ´ultimo caracterizamos la propiedad de que un grafo sea k-coloreable en t´erminos de la pertenencia de un cierto polinomio a un ideal. De este resultado deducimos un algoritmo que determina el n´umero crom´atico de un grafo. Incluimos una implementaci´on en singular del algoritmo propuesto.

The main objective of this work is the study of the graph coloring problem using combinatorial and algebraic tools. We begin by obtaining the upper and lower bounds on the chromatic number of a graph and providing coloring algorithms (not necessarily optimal) of graphs. After this, we study the coloring of planar graphs and prove some weaker versions of the Four Color Theorem, which states that a planar graph is 4-colorable. Finally, we characterize k-colorability of graphs in terms of the membership of a certain polynomial to an ideal. From this result we deduce an algorithm that determines the chromatic number of a graph. We include an implementation in singular of the proposed algorithm.