La conjetura de Steinberg es…¡falsa!

La teoría de grafos es una de las ramas de las matemáticas que más movimiento está teniendo en los últimos años, en lo que se refiere a investigación y a aplicaciones a problemas «reales».

Dentro de la teoría de grafos, los problemas relacionados con coloración de grafos tienen gran interés dentro de los especialistas de esta rama.

Y dentro de los problemas de coloración de grafos, la conjetura de Steinberg ha sido uno de los problemas abiertos que más han interesado a los estudiosos en la materia.

Bien, pues (parece ser que) tenemos resultado para este problema: la conjetura de Steinberg es falsa. En lo que sigue, vamos a dar una idea sobre qué es eso de la coloración de grafos y hablaremos de esta interesante conjetura.

Aunque en Gaussianos ya hemos hablado en otra ocasiones sobre grafos, no está mal recordar algo sobre ellos. Un grafo es un conjunto (distinto del vacío) de puntos, llamados vértices, y un conjunto de líneas , llamadas aristas, cada una de las cuales une dos de sus vértices. Si dos vértices están unidos con al menos una arista, se dice que dichos vértices están conectados.

Un grafo plano es un grafo que puede dibujarse en un plano con la condición de que dos aristas cualesquiera no se cortan en ningún punto que no sea un vértice. En la siguiente imagen podéis ver un grafo plano y uno que no lo es (de hecho es el famoso grafo de Kuratowski ):

Un ciclo en un grafo es una sucesión de vértices en la que cada vértice de la lista está conectado con el siguiente y donde no hay vértices repetidos (excepto el primero y el último). Vamos, lo que todos esperaríamos que fuera un ciclo. La longitud de un ciclo es el número de vértices distintos (equivalentemente, el número de aristas) que contiene. Un ciclo de longitud n se suele denominar n-ciclo. Aquí tenéis dos ciclos, uno de longitud 3 (el verde) y otro de longitud 5 (el rojo):

Una coloración de un grafo es una asignación de etiquetas (colores) a los vértices de dicho grafo de manera que dos vértices conectados tengan distinto color. Si el número de etiquetas es pequeño, suelen usarse colores para etiquetar los vértices. Si este número es grande, suelen usarse números enteros positivos: . Si en la coloración se usan colores, se dice que tenemos una -coloración. Aquí tenéis como ejemplo una 3-coloración del grafo anterior:

The Three Color Problem

Ya tenemos todo lo necesario para introducir el tema principal de esta entrada. La cuestión central de toda esta historia es el coloreado de mapas. El resultado más conocido en relación con esto, como muchos ya sabréis, es el famosísimo teorema de los cuatro colores, demostrado por Kenneth Appel y Wolfgang Haken en 1976.

La primera noticia que se tiene sobre la coloración de mapas con tres colores es un paper de Arthur Cayley de 1879. Ese mismo año, Alfred Kempe también lo trata en su trabajo sobre el teorema de los cuatro colores (que, por cierto, contenía una demostración incorrecta de este resultado); y, más adelante, Percy Heawood también habla de él en sendos trabajos que datan de 1890 y 1898, respectivamente.

Pero es en 1958 cuando el Three Color Problem pasa a tener entidad de problema propio gracias a Herbert Grötzsch, siendo Oystein Ore en 1967 quien lo elevó a los altares. Recomiendo el paper The state of the Three Color Problem [Annals of Discrete Mathematics, 55, 21 1-248 (1993)], de Richard Steinberg, a quienes estén interesados en más datos relacionados con la historia de este problema.

El Three Color Problem pregunta, básicamente, lo siguiente:

¿Bajo qué condiciones pueden ser coloreadas las regiones de un mapa plano con tres colores de manera que no haya dos regiones con frontera común que tengan asignado el mismo color?

Como cada región de un mapa puede interpretarse como un vértice y la frontera común de dos regiones puede asociarse con una arista, un problema de coloreado de mapas puede interpretarse como un problema de coloreado de grafos.

Y por ahí va la cosa, por coloreado de grafos. En 1976, el propio Richard Steinberg establece la conjetura que actualmente lleva su nombre:

Conjetura de Steinberg:

Todo grafo plano que no contenga ni 4-ciclos ni 5-ciclos es 3-coloreable.

Es decir, si un grafo no tiene ciclos de longitud 4 ni ciclos de longitud 5, entonces pueden colorearse sus vértices con 3 colores de manera que no haya vértices conectados que compartan color.

Hasta hace poco, había habido acercamientos a dicha conjetura. Posiblemente, el más interesante surgió a partir de una sugerencia del gran Paul Erdős. Erdős sugirió buscar si existía una constante que cumpliera que todo grafo sin ciclos de longitud era 3-coloreable. Borodin, Glebov, Raspaud y Salavatipour, mejorando resultados anteriores, demostraron en Planar graphs without cycles of length from 4 to 7 are 3-colorable [J. Combin. Theory Ser. B 93 (2005), 303–331] que .

Y más o menos en este punto es en el que estábamos…hasta hace bien poquito (en julio de 2006, se publicaba una supuesta demostración de la veracidad de la conjetura de Steinberg que no fue aceptada como correcta). En abril de este año 2016, Vincent Cohen-Addad, Michael Hebdige, Daniel Král, Zhentao Li y Esteban Salgado ha demostrado que la conjetura de Steinberg es falsa. En su trabajo Steinberg’s Conjecture is False, construyen un contraejemplo para dicha conjetura. Es decir, construyen un grafo plano que no contiene ni 4-ciclos ni 5-ciclos y que no es 3-coloreable. Para ello, comienzan construyendo un grafo (arriba a la izquierda en la imagen) con ciertas propiedades; a partir de él construyen un segundo grafo (arriba a la derecha); y para finalizar construyen un grafo (abajo) a partir de este último que cumple que no tiene ni 4-ciclos ni 5-ciclos y que además no es 3-coloreable:

En el paper que acabo de enlazar podéis ver la demostración de este hecho.

Bien, la conjetura de Steinberg es falsa, problema resuelto. Pero el Three Color Problem sigue abierto, todavía no sabemos si ese cuya búsqueda sugirió Erdős es 7 ó 6. Estaremos atentos a futuras novedades.

Fuentes y enlaces relacionados:

• Steinberg’s Conjecture is False, en The Aperiodical.
• Steinberg’s conjecture en Open Problem Garden.
• Colorings of plane graphs: A survey [Discrete Mathematics 313 (2013) 517–539], de O. V. Borodin.
• Coloración de grafos, en la Wikipedia en español.

Esta entrada participa en la Edición 7.5 del Carnaval de Matemáticas, cuyo anfitrión es el blog Series Divergentes.