En el campo matemático de la teoría de grafos , el teorema de Grötzsch es la afirmación de que todo gráfico plano sin triángulos puede colorearse con sólo tres colores. Según el teorema de los cuatro colores , cada gráfico que se puede dibujar en el plano sin cruces de aristas puede tener sus vértices coloreados usando como máximo cuatro colores diferentes, de modo que los dos puntos finales de cada arista tengan colores diferentes, pero según el teorema de Grötzsch únicamente Se necesitan tres colores para gráficos planos que no contienen tres vértices mutuamente adyacentes.
El teorema lleva el nombre del matemático alemán Herbert Grötzsch , quien publicó su demostración en 1959. La demostración original de Grötzsch era compleja. Berge (1960) intentó simplificarlo pero su demostración fue errónea. [1]
En 1989, Richard Steinberg y Dan Younger formularon y demostraron una versión dual plana del teorema: un gráfico plano de 3 aristas conectado (o más generalmente un gráfico plano sin puentes y como máximo tres cortes de 3 aristas) no tiene ninguna parte. cero 3 flujos . [2]
En 2003, Carsten Thomassen [3] derivó una prueba alternativa de otro teorema relacionado: cada gráfico plano con una circunferencia de al menos cinco se puede colorear en 3 listas . Sin embargo, el teorema de Grötzsch en sí no se extiende desde la coloración hasta la coloración de listas: existen gráficos planos sin triángulos que no se pueden colorear en 3 listas. [4] En 2012, Nabiha Asghar [5] dio una prueba nueva y mucho más simple del teorema que está inspirada en el trabajo de Thomassen.
Un resultado un poco más general es cierto: si un gráfico plano tiene como máximo tres triángulos, entonces se puede colorear en 3 colores. [1] Sin embargo, el gráfico plano completo K 4 , e infinitos otros gráficos planos que contienen K 4 , contienen cuatro triángulos y no se pueden colorear en 3 colores. En 2009, Dvořák , Kráľ y Thomas anunciaron una prueba de otra generalización, conjeturada en 1969 por L. Havel: existe una constante d tal que, si un gráfico plano no tiene dos triángulos dentro de una distancia d entre sí, entonces puede ser coloreado con tres colores. [6] Este trabajo formó parte de la base del Premio Europeo de Combinatoria 2015 de Dvořák . [7]
El teorema no se puede generalizar a todos los gráficos no planos sin triángulos: no todos los gráficos no planos sin triángulos tienen tres colores. En particular, el gráfico de Grötzsch y el gráfico de Chvátal son gráficos sin triángulos que requieren cuatro colores, y el mycielskiano es una transformación de gráficos que se puede utilizar para construir gráficos sin triángulos que requieren un número arbitrariamente alto de colores.
El teorema tampoco se puede generalizar a todos los gráficos planos sin K 4 : no todos los gráficos planos que requieren 4 colores contienen K 4 . En particular, existe un gráfico plano sin 4 ciclos que no puede tener 3 colores. [8]
Una coloración tridimensional de un gráfico G puede describirse mediante un homomorfismo gráfico de G a un triángulo K 3 . En el lenguaje de los homomorfismos, el teorema de Grötzsch establece que todo gráfico plano sin triángulos tiene un homomorfismo con respecto a K 3 . Naserasr demostró que todo gráfico plano sin triángulos también tiene un homomorfismo con respecto al gráfico de Clebsch , un gráfico de 4 cromáticos. Combinando estos dos resultados, se puede demostrar que cada gráfico plano sin triángulos tiene un homomorfismo con respecto a un gráfico de 3 colores sin triángulos, el producto tensorial de K 3 con el gráfico de Clebsch. La coloración del gráfico se puede recuperar componiendo este homomorfismo con el homomorfismo de este producto tensorial a su factor K 3 . Sin embargo, el gráfico de Clebsch y su producto tensorial con K 3 no son planos; no existe un gráfico plano sin triángulos al que todos los demás gráficos planos sin triángulos puedan asignarse mediante un homomorfismo. [9]
Un resultado de Castro et al. (2002) combina el teorema de Grötzsch con la conjetura de Scheinerman sobre la representación de gráficas planas como gráficas de intersección de segmentos de recta . Demostraron que cada gráfico plano sin triángulos puede representarse mediante una colección de segmentos de recta, con tres pendientes, de modo que dos vértices del gráfico son adyacentes si y sólo si los segmentos de recta que los representan se cruzan. Luego se puede obtener una coloración triple del gráfico asignando dos vértices del mismo color siempre que sus segmentos de recta tengan la misma pendiente.
Dado un gráfico plano sin triángulos, se puede encontrar una coloración triple del gráfico en tiempo lineal . [10]