En el campo matemático de la teoría de grafos , el teorema de Grötzsch afirma que todo grafo plano sin triángulos puede colorearse con solo tres colores. Según el teorema de los cuatro colores , todo grafo que se pueda dibujar en el plano sin cruces de aristas puede tener sus vértices coloreados con, 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, solo se necesitan tres colores para los grafos planos que no contienen tres vértices mutuamente adyacentes.
El teorema recibe su 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ó simplificarla, pero su demostración era errónea. [1]
En 1989, Richard Steinberg y Dan Younger formularon y demostraron una versión dual planar del teorema: un grafo planar con 3 aristas conexas (o más generalmente un grafo planar sin puentes y con como máximo tres cortes de 3 aristas) tiene un 3-flujo sin punto cero . [2]
En 2003, Carsten Thomassen [3] derivó una prueba alternativa a partir de otro teorema relacionado: todo grafo plano con circunferencia de al menos cinco es coloreable mediante 3 listas . Sin embargo, el teorema de Grötzsch en sí no se extiende de la coloración a la coloración mediante listas: existen grafos planos sin triángulos que no son coloreables mediante 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 ligeramente más general es cierto: si un grafo plano tiene como máximo tres triángulos, entonces es 3-coloreable. [1] Sin embargo, el grafo plano completo K 4 , y una infinidad de otros grafos planos que contienen K 4 , contienen cuatro triángulos y no son 3-coloreables. 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 grafo plano no tiene dos triángulos a una distancia d entre sí, entonces puede colorearse con tres colores. [6] Este trabajo formó parte de la base para el Premio Europeo de Combinatoria de 2015 de Dvořák . [7]
El teorema no se puede generalizar a todos los grafos no planos sin triángulos: no todos los grafos no planos sin triángulos son 3-coloreables. En particular, el grafo de Grötzsch y el grafo de Chvátal son grafos sin triángulos que requieren cuatro colores, y el Mycielskian es una transformación de grafos que se puede utilizar para construir grafos sin triángulos que requieren una cantidad arbitrariamente alta de colores.
El teorema tampoco se puede generalizar a todos los grafos planos libres de K 4 : no todo grafo plano que requiere 4 colores contiene K 4 . En particular, existe un grafo plano sin 4-ciclos que no puede tener 3 colores. [8]
Una coloración 3 de un grafo G puede describirse mediante un homomorfismo de grafo de G a un triángulo K 3 . En el lenguaje de los homomorfismos, el teorema de Grötzsch establece que todo grafo plano libre de triángulos tiene un homomorfismo a K 3 . Naserasr demostró que todo grafo plano libre de triángulos también tiene un homomorfismo al grafo de Clebsch , un grafo 4-cromático. Combinando estos dos resultados, puede demostrarse que todo grafo plano libre de triángulos tiene un homomorfismo a un grafo 3-coloreable libre de triángulos, el producto tensorial de K 3 con el grafo de Clebsch. La coloración del grafo puede entonces recuperarse componiendo este homomorfismo con el homomorfismo de este producto tensorial a su factor K 3 . Sin embargo, el grafo de Clebsch y su producto tensorial con K 3 son ambos no planos; no existe un grafo plano libre de triángulos al cual cualquier otro grafo plano libre de triángulos pueda ser mapeado mediante un homomorfismo. [9]
Un resultado de de Castro et al. (2002) combina el teorema de Grötzsch con la conjetura de Scheinerman sobre la representación de grafos planares como grafos de intersección de segmentos de línea . Demostraron que cada grafo planar sin triángulos puede representarse mediante una colección de segmentos de línea, con tres pendientes, tales que dos vértices del grafo son adyacentes si y solo si los segmentos de línea que los representan se cruzan. Entonces se puede obtener una coloración triple del grafo asignando a dos vértices el mismo color siempre que sus segmentos de línea tengan la misma pendiente.
Dado un gráfico plano sin triángulos, se puede encontrar una coloración tridimensional del gráfico en tiempo lineal . [10]