Coloraciones de grafos: grafos planos y polinomio cromático

Abstract

Colorear un grafo significa asignar “colores” a sus vértices de modo que dos vértices adyacentes nunca tengan el mismo color. Se trata de un problema muy clásico por su relación por ejemplo con las coloraciones de mapas y el famoso Teorema de los Cuatro Colores, pero tiene también aplicaciones prácticas, por ejemplo cuando se quiere dividir un conjunto en grupos pero hay ciertas incompatibilidades entre elementos, que no pueden estar en el mismo grupo. El Teorema de los Cuatro Colores, a su vez, relaciona las coloraciones con la planaridad y con los teoremas de Kuratowski y Wagner, que la caracterizan. En este trabajo, después de introducir los conceptos fundamentales, tenemos dos objetivos: Por un lado, dar la demostración completa de los Teoremas de Kuratowski y Wagner. Por otro lado, estudiar el polinomio cromático de un grafo, que nos dice de cuántas maneras se puede colorear. Para su cálculo usaremos técnicas de borrado y contracción en algunos ejemplos concretos.

Coloring a graph means assigning “colors” to its vertices so that two adjacent vertices never have the same color. This is a very classical problem because of its relation to, for example, map colorings and the famous Four Color Theorem, but it also has practical applications, for example when you want to divide a set into groups but there are certain incompatibilities between elements, which cannot be in the same group. The Four Color Theorem, in turn, relates colorings to planarity and to Kuratowski’s and Wagner’s theorems, which characterize it. In this work, after introducing the fundamental concepts, we have two objectives: On the one hand, to give the complete proof of Kuratowski’s andWagner’s Theorems. On the other hand, to study the chromatic polynomial of a graph, which says how many different colorings it has. To compute it we use deletion and contraction techniques in some specific examples.