Bajo su apariencia lúdica, incluso infantil, las cuestiones de coloreado en el plano plantean en realidad temibles desafíos a matemáticos e informáticos. Hubo que esperar más de cien años para poder afirmar que cualquier mapa plano dividido en regiones conexas puede colorearse con cuatro colores de modo que dos regiones limítrofes reciban siempre colores distintos. Es el famoso teorema de los cuatro colores, enunciado ya en 1852 y cuya demostración, realizada en 1976 por Kenneth Appel y Wolfgang Haken, requería un intenso procesamiento informático, por lo que no suscitaba consenso. En 2005, Georges Gonthier y Benjamin Werner publicaron una nueva demostración, formal esta vez —aunque seguía utilizando el ordenador de manera crucial—; hoy esta demostración goza de mucha mayor aceptación en la comunidad. Pero, aunque cuatro colores bastan, no son en absoluto necesarios… Así, algunos mapas podrán colorearse con tres colores, o incluso con solo dos.

Construcción rápida de un teselado hexagonal.

Matemáticas mientras ensartamos cuentas --------------------------------
Dos colores pueden bastar para hacer un collar abierto sin que dos cuentas del mismo color estén en contacto. Basta con alternar los colores… Ahora cerremos sobre sí mismo este segmento de cuentas coloreadas. Para respetar la condición, el color del comienzo del segmento del collar debe ser distinto del color del final. Por tanto, el número de cuentas utilizadas ha de ser necesariamente par. Si el collar tiene un número impar de cuentas, será necesario disponer de un tercer color…
Volvamos ahora a un mapa trazado en el plano, o a un teselado. Como en una vidriera, se considera que dos regiones son vecinas si comparten una frontera común —una línea que no se reduce a un punto—.
Se distinguen esencialmente los teselados regulares, compuestos por celdas idénticas o isométricas —cuadriláteros, hexágonos…—, y los teselados irregulares, compuestos por celdas no isométricas y que, además, presentan a veces lagunas —ausencias de contacto—. Para colorear los teselados regulares bastan tres colores, y a veces dos. Así, para colorear un teselado hexagonal regular —en «panal de abeja»—, basta con apilar alternadamente segmentos siguiendo «filas» ordenadas coloreadas en azul, verde y rojo. Este teselado no puede modificarse sin crear irregularidades, cosa que no ocurre con el plano teselado mediante cuadriláteros.
Aislamos en este teselado un grupo de celdas estructurado en torno a un elemento central, el pivote, rodeado por una corona —volvemos aquí a nuestro collar inicial— compuesta por un número par de celdas —numeradas del 1 al 6—, alternativamente verdes y azules. Este grupo demuestra que son necesarios tres colores.

Un grupo de celdas, con un pivote central, 0 —en rojo—.

Se les asocia de forma natural un grafo.
La representación de un teselado mediante un grafo tiene la ventaja de mostrar las relaciones de contigüidad entre las celdas sin atender a su geometría. Cada vértice del grafo representa una celda —con su color— y cada arista materializa una frontera del teselado. Esta representación garantiza que las propiedades de la agrupación anterior —pivote y corona— se aplican al teselado regular en su totalidad. En efecto, al superponer la agrupación considerada con todos los demás pivotes del teselado se observa que los colores de las coronas se corresponden: las características locales de la agrupación que comprende las piezas numeradas del 0 al 6 se extienden a todo el plano.

Del ámbito local al global.

En el teselado inicial, todos los pivotes están coloreados de rojo. Las celdas verdes y azules forman las coronas, ocupan las mismas posiciones relativas, como en un reloj, y participan en las agrupaciones adyacentes.
-
Dígalo con cuadriláteros -------------------------------
Como en la estructura de panal de abeja, puede construirse un teselado regular del plano con cuadriláteros: basta con apilar alternadamente sucesiones de segmentos siguiendo «filas» ordenadas coloreadas en azul, verde y rojo, mediante volteos o desplazamientos. Este teselado puede adoptar dos configuraciones diferentes.

Primera configuración a la izquierda; segunda configuración a la derecha.

El grafo asociado.

El primer caso es idéntico a la red hexagonal: una corona de seis piezas rodea el pivote. Esta corona comprende seis celdas —un número par—, lo que proporciona en total tres colores distintos. En el segundo caso, solo son necesarios dos colores para el coloreado. La corona está compuesta, desde luego, por ocho celdas —también un número par—, pero aquí el pivote puede recibir un color compatible con las condiciones.
Cuando los elementos del plano dejan de ser isométricos, la regularidad del coloreado del plano se resiente. Para colorear el plano de la figura siguiente, basta con elegir un grupo de celdas con su pivote. Por ejemplo, la corona alrededor de la celda 0 contiene siete celdas. Puesto que su número es impar, será necesario utilizar cuatro colores para colorear esta primera selección. Demos al pivote 0 el color rojo y, después, el azul a las celdas 1, 3 y 5, alternándolo con el verde para las celdas 2, 4 y 6. Pero, como las celdas 7 y 1 son vecinas, hay que añadir un nuevo color —el amarillo— a la paleta para completar el coloreado de este grupo.
Para continuar el coloreado, seleccionemos celdas adyacentes al primer grupo. Por ejemplo, elegiremos la celda 1 —azul— como pivote de la nueva agrupación. Las celdas que pertenecen a la nueva corona son las numeradas 2, 0 y 7. Para completar la corona, basta con tomar las cuatro celdas siguientes, cada una de las cuales está en contacto con el nuevo pivote azul: 11, 12, 13 y 8 —que se colorearán de rojo—. Esta corona, ya completa, tiene un número impar de celdas; tomará prestado un color —el amarillo— de la agrupación anterior.
¿Y si el mapa presenta «agujeros», regiones ausentes? La ausencia de una celda en un teselado irregular es similar al caso del teselado de dos colores. La corona continúa más allá de la conexión que falta. Esta laguna está representada en el esquema anterior por la celda 8, sin colorear. El siguiente grafo muestra las consecuencias.
-
Una laguna en el teselado -------------------------
Si la celda 8 no existe, nos encontramos ante una laguna alrededor del pivote 2. La corona está entonces compuesta por las celdas 1, 13, 9, 10, 15, 3 y 0.
Si 8 está presente, la corona evita la celda 13 y se conecta a través de 1, 8 y 9. La celda 8 será roja para conservar una paleta mínima de colores. En cualquier caso, el teorema de los cuatro colores nos asegura que tal coloreado es posible…