Grafos, dualidad y número cromático
Esta actividad pertenece al libro de GeoGebra Teselados regulares euclídeos, elípticos e hiperbólicos.
Un grafo no es más que un conjunto de puntos (llamados nodos o vértices) y conexiones entre ellos (llamadas aristas o arcos).
Un grafo plano es un grafo cuyos vértices y aristas se pueden representar en un plano de modo que ninguna arista se cruce con otra. A menudo, las aristas dividen el plano en regiones (de área finita o infinita, y en número finito o infinito).
Un polígono de n lados es un caso particular de grafo, con n puntos (los vértices) y n conexiones (los lados), que divide el plano en dos regiones (una interior y otra exterior). Una teselación plana es un grafo plano con infinitos nodos y aristas que delimitan infinitas regiones.
Si en un grafo plano sustituimos cada región por un punto, y cada arista entre dos regiones vecinas por una arista que las conecte, obtenemos el grafo dual. Por ejemplo, el grafo dual de un triángulo (tres puntos, tres aristas, dos regiones) será el grafo formado por dos puntos conectados por tres aristas (dos puntos, tres aristas, tres regiones).
![[size=85]A la izquierda, un triángulo (tres vértices) divide al plano en dos regiones. A la derecha, su grafo dual (dos vértices) divide al plano en tres regiones. Observa que el grafo dual del de la izquierda vuelve a ser el de la derecha.[/size]](https://www.geogebra.org/resource/shdac4ct/DVV2JK8O9731jabp/material-shdac4ct.png)
El grado de un vértice es el número de aristas que conectan con él. Se dice que un grafo es q-regular si todos sus vértices tienen grado q.
Por lo tanto, una teselación regular {p, q}, es decir, una teselación de polígonos regulares de p lados donde q se encuentran en cada vértice, es un grafo q-regular cuyo dual es p-regular.
Dada una teselación regular {p, q}, llamamos teselación dual a la teselación regular {q, p}, pues los grafos duales de ambas son duales entre sí.
El número cromático de un grafo es el mínimo número de colores que podemos asignar a sus vértices de modo que no haya dos conectados por una arista que tengan el mismo color. Por ejemplo, el número cromático de un polígono es 2 si tiene un número par de vértices, y 3 si tiene un número impar.
El número cromático de una teselación es el mínimo número de colores que se necesitan para pintar todas las regiones sin que haya dos vecinas que tengan el mismo color. Es decir, es el número cromático de su grafo dual.
El número cromático de una teselación regular {p, q} es 2 cuando q sea par. Si q vale 3 y p es impar, hacen falta 4 colores. En los demás casos, el número cromático es 3.
Autor de la actividad: Rafael Losada.