El matemático ruso Yaroslav Shitov ha demostrado que una conjetura con más de 50 años de historia sobre un problema de la teoría de grafos no es correcta. Y lo ha hecho dando un contraejemplo: presentando un caso en el que no se cumple lo que la conjetura predecía.
Los grafos, que se componen de vértices y aristas, son una de las estructuras más simples y más versátiles de las matemáticas, y tiene muchísimas aplicaciones (diseño de redes de comunicaciones, distribución de mercancías, planificación de la producción, etc.).
En este campo, uno de los problemas más estudiados ha sido siempre el de encontrar el mínimo número de colores que se pueden asignar a los vértices de manera que no haya dos con el mismo color unidos por una arista.
Los problemas de coloración, aunque parezca mentira, pueden ser tremendamente complicados. Su historia se remonta a mediados del s. XIX cuando uno de los hermanos Guthrie (no está claro cuál), conjeturó que cualquier grafo que se pueda dibujar en el plano de forma que dos aristas distintas no se crucen, salvo en un vértice común, se puede colorear siempre con cuatro colores o menos. Es el conocido como problema del mapa de los cuatro colores que cerca de 125 años después, allá por 1976, resolvieron definitivamente los matemáticos Kenneth Appel y Wolfgang Hanken. En 1966 Stephen Hedetniemi en su tesis doctoral conjeturó también al respecto: dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial GXH es el menor de los colores necesarios para colorear G y H. Este grafo se obtiene combinando de cierta forma los vértices y aristas de G y H.
Esta última conjetura ha sido válida hasta hace un mes aproximadamente, cuando Yaroslav Shitov (a sus 30 años de edad) ha conseguido demostrar formalmente que es falso y porqué. Encontrado dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H, aunque los grafos que ha utilizado en su breve artículo (de tan solo dos páginas y media) son enormes, han servido para conseguir lo que no se había logrado hasta ahora: nadie había podido demostrar la conjetura de Hedetniemi, y no había sido posible porque era falsa.