Grafos

Coloreando grafos

Vamos ahora a introducir un ingrediente nuevo en este recorrido por la Teor´ıa de Grafos: vamos a “colorear” los v´ertices de un grafo, con unas ciertas reglas que veremos en un momento. El objetivo es abordar la cuesti´on de contar listas con restricciones (en particular, el problema de los horarios que plantea´bamos al principio del cap´ıtulo).
Tenemosun grafo G y un conjunto de colores S = {a, b,... }. Una coloracio´n de G con los colores de S consistir´a en asignar a los v´ertices de G elementos de S (“colores”) de manera que los extremos de cada arista reciban colores distintos. Formalmente, una coloracio´n de G con colores de S es una aplicaci´on
γ : V (G) −→ S

de forma que γ(v) = γ(w) si {v, w}∈ A(G). El valor de γ(v) es el color querecibe el v´ertice
v en la coloraci´on.

Definici´on 8.13 El nu´mero cromatico de un grafo G, χ(G), ser´a el nu´mero m´ınimo de colores necesario para colorear G.

Un problema cl´asico en este contexto es el llamado problema de los cuatro colores. Esta cuesti´on concreta es la que da lugar a la terminolog´ıa de los colores. Aunque la estudiaremos en detalle en el cap´ıtulo , vamos apresentarla aqu´ı de manera informal.
Tenemos un mapa con un cierto nu´mero de pa´ıses y sus fronteras correspondientes, y queremos colorearlo de manera que pa´ıses vecinos reciban, para poder distinguirlos, colores distintos. Para analizar esta cuesti´on, usamos grafos para representar la informaci´on relevante: los pa´ıses que aparecen y una relacio´n binaria, la de vecindad. Elconjunto de pa´ıses ser´a el de v´ertices, y dibujaremos una arista entre dos v´ertices si los pa´ıses que representan son vecinos. De esta manera obtenemos un grafo, y el problema de asignar colores a los pa´ıses se traduce en el de colorear el grafo.
Hay que tener cierto cuidado con la construcci´on del grafo: dos pa´ıses pueden tener m´as de un trozo de frontera comu´n (Espan˜a y Francia,por ejemplo, donde Andorra separa en dos la frontera pirenaica), as´ı que a veces tendremos que usar aristas mu´ltiples. O quizas a un pa´ıs le pueden corresponder varias regiones separadas (por ejemplo, unas islas); cada una de estas regiones deber´ıa entonces ser considerada como un pa´ıs distinto. En todo caso, y esto es lo importante, el grafo que se obtiene es muy especial: es loque se llama un grafo plano (en el cap´ıtulo 15 lo definiremos con cuidado).
El problema cl´asico al que alud´ıamos es el de verificar que todo mapa puede ser coloreado con s´olo cuatro colores; en otras palabras, que el nu´mero crom´atico del grafo (plano) obtenido a partir de un mapa de la forma descrita anteriormente es menor o igual que cuatro. Por ejemplo, en el mapa


A

B CD


cuyo grafo asociado ser´ıa
A B




C D

es decir, un K4 , hacen falta cuatro colores

Pero volvamos con nuestro problema general de coloraciones de grafos. Algunas observa- ciones inmediatas sobre el nu´mero crom´atico son las siguientes:

1. Para todo grafo G, χ(G) ≤ |V | , porque siempre podremos colorear con |V | colores,asignando a cada v´ertice un color distinto. E´ sta es, obviamente, la forma menos efectiva de colorear.
2. Si el grafo contiene al menos una arista, necesitaremos dos colores como m´ınimo; es decir, si |A|≥ 1, entonces χ(G) ≥ 2.
3. Si G contiene a G como subgrafo, entonces

χ(G) ≥ χ(G ) ,

porque al menos necesitaremos χ(G ) colores para colorear el subgrafo (y quiza´s m´as para elresto). Los ejemplos m´as relevantes de subgrafos que habremos de buscar dentro de un grafo para obtener informacio´n sobre su nu´mero crom´atico son los completos y los ciclos de orden impar, cuyos nu´meros crom´aticos obtendremos pronto (en el ejem- plo 8.4.1).
4. Si G tiene k componentes conexas, G1 , G2 ,... , Gk que tienen nu´meros crom´aticos
χ(G1 ), χ(G2 ),... , χ(Gk...