Teorema de los cinco colores

El teorema de los cinco colores es un resultado de la teoría de grafos que establece que, dado un plano dividido en regiones, como un mapa político de los países del mundo, las regiones pueden colorearse con no más de cinco colores de tal manera que dos regiones adyacentes no reciban el mismo color. Adyacente significa que dos regiones comparten un límite común de longitud distinta de cero (es decir, no simplemente una esquina donde se encuentran tres o más regiones). ^{[ 2 ]}

El teorema de los cinco colores se deduce del teorema de los cuatro colores , más fuerte, pero es considerablemente más fácil de demostrar . Fue demostrado por primera vez por Percy John Heawood en 1890, basándose en una supuesta demostración del teorema de los cuatro colores presentada por Alfred Kempe en 1879. Dicha demostración se consideró correcta durante 11 años, pero Heawood descubrió un error; sin embargo, logró dar una demostración correcta del teorema de los cinco colores, más débil, basándose en el trabajo de Kempe. La primera demostración correcta del teorema de los cuatro colores se encontró recién en 1976.

En primer lugar, se asocia un grafo planar simple.${\displaystyle G}$En el mapa dado, se coloca un vértice en cada región del mapa y luego se conectan dos vértices con una arista si y solo si las regiones correspondientes comparten un borde común. El problema se traduce entonces en un problema de coloración de grafos: hay que pintar los vértices del grafo de manera que ninguna arista tenga extremos del mismo color.

Porque${\displaystyle G}$es un grafo planar simple , es decir, puede estar incrustado en el plano sin intersecarse con aristas, no tiene dos vértices que compartan más de una arista y no tiene bucles, entonces se puede demostrar (usando la característica de Euler del plano) que debe tener un vértice compartido por como máximo cinco aristas. (Nota: Este es el único lugar donde se usa la condición de cinco colores en la demostración. Si esta técnica se usa para demostrar el teorema de los cuatro colores, fallará en este paso, ya que hay algunos grafos que no tienen ningún vértice compartido por como máximo cuatro aristas. Un contraejemplo notable es el grafo icosaédrico : como grafo planar y 5-regular, no tiene ningún vértice compartido por como máximo cuatro aristas). Encuentra tal vértice y llámalo${\displaystyle v}$.

Ahora retira${\displaystyle v}$de${\displaystyle G}$El gráfico${\displaystyle G'}$obtenido de esta manera tiene un vértice menos que${\displaystyle G}$, por lo que podemos asumir por inducción que se puede colorear con solo cinco colores. Si el coloreado no utilizara los cinco colores en los cinco vértices vecinos de${\displaystyle v}$, se puede colorear${\displaystyle G}$con un color que no utilizan los vecinos. Así que ahora miren esos cinco vértices.${\displaystyle v_{1}}$,${\displaystyle v_{2}}$,${\displaystyle v_{3}}$,${\displaystyle v_{4}}$,${\displaystyle v_{5}}$que estaban adyacentes a${\displaystyle v}$en orden cíclico (que depende de cómo escribamos G). Por lo tanto, podemos suponer que${\displaystyle v_{1}}$,${\displaystyle v_{2}}$,${\displaystyle v_{3}}$,${\displaystyle v_{4}}$,${\displaystyle v_{5}}$están coloreados con los colores 1, 2, 3, 4, 5 respectivamente.

Ahora consideremos el subgrafo${\displaystyle G_{1,3}}$de${\displaystyle G'}$consta de los vértices que están coloreados solo con los colores 1 y 3 y las aristas que los conectan. Para ser claros, cada arista conecta un vértice de color 1 con un vértice de color 3 (esto se llama cadena de Kempe ). Si${\displaystyle v_{1}}$y${\displaystyle v_{3}}$yacen en diferentes componentes conectados de${\displaystyle G_{1,3}}$, podemos intercambiar los colores 1 y 3 en el componente que contiene${\displaystyle v_{1}}$sin afectar la coloración del resto de${\displaystyle G'}$. Esto libera el color 1 para${\displaystyle v}$completando la tarea. Si, por el contrario,${\displaystyle v_{1}}$y${\displaystyle v_{3}}$yacen en el mismo componente conectado de${\displaystyle G_{1,3}}$, podemos encontrar un camino en${\displaystyle G_{1,3}}$uniéndolos que consisten únicamente en vértices de color 1 y 3.

Ahora pasemos al subgrafo${\displaystyle G_{2,4}}$de${\displaystyle G'}$que consiste en los vértices que están coloreados solo con los colores 2 y 4 y las aristas que los conectan, y aplicamos los mismos argumentos que antes. Entonces, o bien podemos invertir la coloración 2-4 en el subgrafo de${\displaystyle G_{2,4}}$que contiene${\displaystyle v_{2}}$y pintura${\displaystyle v}$color 2, o podemos conectar${\displaystyle v_{2}}$y${\displaystyle v_{4}}$con un camino que consta únicamente de vértices de color 2 y 4. Dicho camino se intersectaría con el camino de color 1-3 que construimos anteriormente, ya que${\displaystyle v_{1}}$a través de${\displaystyle v_{5}}$estaban en orden cíclico. Esto contradice claramente la planaridad del grafo.

Entonces${\displaystyle G}$De hecho, puede ser de cinco colores, contrariamente a la suposición inicial.

Varios autores, comenzando con Lipton y Miller en 1978, han estudiado algoritmos eficientes para la coloración de cinco colores en grafos planares. El algoritmo de Lipton y Miller requirió tiempo.${\displaystyle O(n\log n)}$, ^{[ 3 ]} pero investigadores posteriores redujeron el límite de tiempo a${\displaystyle O(n)}$. ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} La versión que aparece a continuación proviene de un artículo de 1996 de Robertson, Sanders, Seymour y Thomas, que la describe brevemente en relación con un método más lento.${\displaystyle O(n^{2})}$Algoritmo de tiempo para la coloración de cuatro colores. ^{[ 9 ]} El algoritmo descrito aquí opera sobre multigrafos y se basa en la capacidad de tener múltiples copias de aristas entre un único par de vértices. Se basa en el teorema de Wernicke , que establece lo siguiente:

Teorema de Wernicke : Supongamos que G es planar, no vacío, no tiene caras delimitadas por dos aristas y tiene un grado mínimo de 5. Entonces G tiene un vértice de grado 5 que es adyacente a un vértice de grado como máximo 6.

Utilizaremos una representación del grafo en la que cada vértice mantiene una lista enlazada circular de vértices adyacentes, en orden planar en sentido horario.

En teoría, el algoritmo es recursivo: reduce el grafo a uno más pequeño con un vértice menos, lo colorea con cinco colores y luego usa esa coloración para determinar la coloración del grafo más grande en tiempo constante. En la práctica, en lugar de mantener una representación gráfica explícita para cada grafo reducido, eliminaremos vértices del grafo a medida que avancemos, los agregaremos a una pila y luego los colorearemos al extraerlos de la pila al final. Mantendremos tres pilas:

• S ₄ : Contiene todos los vértices restantes con grado como máximo cuatro, o grado cinco y como máximo cuatro vértices adyacentes distintos (debido a múltiples aristas ).
• S ₅ : Contiene todos los vértices restantes que tienen grado cinco, cinco vértices adyacentes distintos y al menos un vértice adyacente con grado como máximo seis.
• S _d : Contiene todos los vértices eliminados del grafo hasta el momento, en el orden en que fueron eliminados.

El algoritmo funciona de la siguiente manera:

1. En el primer paso, convertimos todas las aristas múltiples en aristas simples, de modo que el grafo sea simple. A continuación, iteramos sobre los vértices del grafo, colocando en la pila correspondiente cualquier vértice que cumpla las condiciones de S ₄ o S ₅ .
2. A continuación, mientras S ₄ no esté vacío, extraemos v de S ₄ y lo eliminamos del grafo, colocándolo en S _d , junto con una lista de sus vecinos en ese momento. Verificamos cada antiguo vecino de v y lo colocamos en S ₄ o S ₅ si ahora cumple las condiciones necesarias.
3. Cuando S ₄ se vacía, sabemos que nuestro grafo tiene un grado mínimo de cinco. Si el grafo está vacío, pasamos al paso final 5 a continuación. De lo contrario, el teorema de Wernicke nos dice que S ₅ no está vacío. Eliminamos v de S ₅ , lo borramos del grafo y consideramos v ₁ , v ₂ , v ₃ , v ₄ , v ₅ como los antiguos vecinos de v en orden planar en sentido horario, donde v ₁ es el vecino de grado como máximo 6. Verificamos si v ₁ es adyacente a v ₃ (lo cual podemos hacer en tiempo constante debido al grado de v ₁ ). Hay dos casos:
   1. Si v1 no es adyacente a v3 , podemos fusionar estos dos vértices en uno solo. Para ello, eliminamos _v de ambas listas _de adyacencia circulares y luego unimos las dos listas en una sola en el punto donde se encontraba v anteriormente. Siempre que v mantenga una referencia a su posición en cada lista, esto se puede hacer en tiempo constante. Es posible que esto cree caras delimitadas por dos aristas en los dos puntos donde se unen las listas; eliminamos una arista de dichas caras. Después de hacer esto, agregamos v3 a Sd _, junto con una nota que indica que _v1 es el vértice con _el que se fusionó. Cualquier vértice afectado por la fusión se agrega o elimina de las pilas según corresponda.
   2. _{De lo} contrario, v2 queda dentro de la cara delimitada por v , v1 y v3 _. Por consiguiente, v2 no _{puede ser} adyacente a v4 , _{que queda fuera de} esta cara. Fusionamos v2 y v4 de la misma manera que _fusionamos v1 y _v3 anteriormente _.
4. Ve al paso 2.
5. En este punto, S4 _, S5 _y el grafo están vacíos. Eliminamos vértices de Sd _. Si el vértice se fusionó con otro vértice en el paso 3, el vértice con el que se fusionó ya estará coloreado, y le asignamos el mismo color. Esto es válido porque solo fusionamos vértices que no eran adyacentes en el grafo original. Si lo eliminamos en el paso 2 porque tenía como máximo 4 vértices adyacentes, todos sus vecinos en el momento de su eliminación ya estarán coloreados, y podemos simplemente asignarle un color que ninguno de sus vecinos esté usando.

Kainen (1974) proporciona una demostración simplificada del teorema de los cinco colores, basada en la no planaridad de K ₆ (el grafo completo con 6 vértices) y los menores de grafos . Esta demostración se generaliza a grafos que pueden hacerse planares eliminando 2 aristas. ^{[ 10 ]}

• Teorema de los cuatro colores

• Heawood, PJ (1890), "Teorema del color del mapa" , Quarterly Journal of Pure and Applied Mathematics, Oxford , vol.  24, pp . 332–338