El teorema de Grötsch es la afirmación de que cualquier gráfico plano sin triángulos se puede colorear con tres colores. De acuerdo con el teorema de los cuatro colores , para cualquier gráfico que se pueda dibujar en el plano sin que se crucen las aristas, es posible colorear sus vértices con un máximo de cuatro colores diferentes para que dos extremos cualquiera de cualquier arista tengan colores diferentes. De acuerdo con el teorema de Grötzsch, solo tres colores son suficientes para gráficos planos que no contienen tres vértices conectados.
El teorema lleva el nombre del matemático alemán Herbert Grötsch , quien publicó la demostración en 1959. La prueba original de Grötsch era complicada. Berge [1] trató de simplificarlo, pero su prueba contenía errores [2] .
En 2003, Carsten Thomassen [3] dio una prueba alternativa, a partir de un teorema relacionado: cualquier gráfico plano con una circunferencia de al menos cinco tiene un color de 3 prescrito . Sin embargo, el teorema de Grötzsch en sí mismo no se extiende de un coloreado a un coloreado prescrito—hay gráficos planos libres de triángulos que no tienen un coloreado de 3 colores prescrito [4] . En 1989, Richard Steinberg y Dan Junger [5] dieron la primera demostración correcta en inglés de la versión dual de este teorema. En 2012, Nabiha Asghar [6] dio una prueba nueva y mucho más simple del teorema, 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 con 3 colores [2] . Sin embargo, el gráfico plano completo K 4 e infinitamente muchos otros gráficos planos que contienen K 4 contienen cuatro triángulos y no son 3-coloreables. En 2009, Dvorak, Kralj y Thomas anunciaron la prueba de otra generalización, que fue propuesta en 1969 por la conjetura de L. Havel: existe una constante d tal que si un gráfico plano tiene dos triángulos a una distancia máxima de d , entonces el gráfico se puede colorear con tres colores [7] . Este trabajo formó parte de la base del Premio Europeo de Combinatoria Dvorak 2015 [8]
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 se pueden colorear en 3 colores. En particular, las gráficas de Grötzsch y Chwátala son gráficas sin triángulos pero requieren cuatro colores, y Mycelskian es una transformación de gráficas que se puede usar para construir gráficas sin triángulos que requieren una cantidad arbitrariamente grande de colores.
El teorema tampoco se puede generalizar a todos los gráficos planos libres de 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 ser de 3 colores [9] .
Una coloración de 3 colores de un gráfico G se puede describir mediante un homomorfismo gráfico de G en un triángulo K 3 . En el lenguaje de los homomorfismos, el teorema de Grötzsch establece que cualquier gráfico plano libre de triángulos tiene un homomorfismo para el gráfico K 3 . Nasserasr demostró que cualquier gráfico plano libre de triángulos también tiene un homomorfismo para el gráfico de Clebsch , un gráfico de 4 cromáticas. Al combinar estos dos resultados, se puede demostrar que cualquier gráfico plano libre de triángulos tiene un homomorfismo a un gráfico de 3 colores libre de triángulos, el producto tensorial K 3 con el gráfico de Clebsch. La coloración del gráfico se puede obtener superponiendo este homomorfismo con el homomorfismo de su producto tensorial en 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 en el que cualquier otro gráfico plano sin triángulos pueda ser mapeado mediante un homomorfismo [10] [11] .
El resultado de Castro, Cobos, Dan, Márquez [12] combina el teorema de Grötzsch con la conjetura de Scheinerman sobre representaciones de grafos planos como grafos de intersección de segmentos . Demostraron que cualquier gráfico plano libre de triángulos puede representarse mediante un conjunto de segmentos de línea con tres pendientes posibles, de modo que dos vértices del gráfico son adyacentes si y solo si los segmentos de línea que los representan se cruzan. Entonces se puede obtener una coloración de 3 de un gráfico asignando dos vértices del mismo color si sus segmentos de línea tienen la misma pendiente.
Dado un gráfico plano libre de triángulos, se puede obtener una coloración de 3 del gráfico en tiempo lineal [13] .