Resumen
Un grafo es un par formado por dos conjuntos, uno de vértices y
otro de aristas, las cuales unen a los vértices. Normalmente,
representamos a los vértices y las aristas de un grafo por puntos y
segmentos, respectivamente. Una propiedad interesante de los grafos es que
se pueden colorear. Una coloración del grafo consiste en asignar colores a
los vértices de manera que si dos de ellos están unidos mediante una
arista no pueden tener el mismo color. De manera similar podemos colorear
las aristas de un grafo. En relación al coloreado de grafos encontramos
muchos resultados interesantes relacionados con el número mínimo de
colores necesarios para conseguir una coloración del grafo. Este número,
se llama nímero cromático del grafo cuando hablamos de coloración de
vértices o índice cromático si hablamos de coloración en aristas.
Además del número de colores, también es interesante saber cuántas
coloraciones distintas admite el grafo. Esta cuestión está íntimamente
ligada a lo que se conoce como polinomio cromático del grafo, el cual, en
algunas ocasiones, es bastante complicado de calcular. Otra propiedad
interesante de los grafos es la planaridad. Llegados a este punto, tenemos
que admitir los llamados multigrafos, que, a diferencia de los grafos,
admiten que una arista una a un vértice consigo mismo o que dos vértices
estén unidos por dos aristas diferentes. Esto nos permite construir el
grafo dual de un grafo plano. Un resultado muy conocido sobre grafos
planos es la famosa Fórmula de Euler, que relaciona el número de vértices,
aristas y caras de un grafo. El estudio del coloreado y la planaridad de
grafos nos permite enunciar el famoso Teorema de los 4 colores, que nos
dice que todo mapa plano es 4-colorable. Existen resultados equivalentes
usando 5 y 6 colores, los cuales son bastante sencillos de probar, sobre
todo en comparación con el de los 4 colores, cuya demostración es bastante
compleja y extensa.