En el campo matemático de la teoría de grafos , el teorema de Grötzsch es la afirmación de que cada grafo plano sin triángulos se puede colorear con solo tres colores. De acuerdo con el teorema de los cuatro colores , cada gráfico que se puede dibujar en el plano sin cruces de bordes puede tener sus vértices coloreados usando como máximo cuatro colores diferentes, de modo que los dos extremos de cada borde tengan colores diferentes, pero según el teorema de Grötzsch solo se necesitan tres colores para gráficos planos que no contienen tres vértices mutuamente adyacentes.
Historia
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 era errónea. [1]
En 2003, Carsten Thomassen [2] derivó una demostración alternativa de otro teorema relacionado: cada gráfico plano con una circunferencia de al menos cinco es colorable en 3 listas . Sin embargo, el teorema de Grötzsch en sí mismo no se extiende desde la coloración hasta la coloración de listas: existen gráficos planos sin triángulos que no son coloreables en 3 listas. [3] En 2012, Nabiha Asghar [4] dio una prueba nueva y mucho más simple del teorema que está inspirada en el trabajo de Thomassen.
En 1989, Richard Steinberg y Dan Younger [5] dieron la primera demostración correcta, en inglés, de la versión dual de este teorema.
Clases más grandes de gráficos
Un resultado un poco más general es cierto: si un gráfico plano tiene como máximo tres triángulos, entonces es 3-coloreable. [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 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 gráfico plano no tiene dos triángulos a 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 todas las gráficas sin triángulos no planas: no todas las gráficas sin triángulos no planas son 3-coloreables. 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 Mycielskian es una transformación de gráficos que se puede usar para construir gráficos sin triángulos que requieren números arbitrariamente altos de colores.
El teorema tampoco puede generalizarse a todas las gráficas planas libres de K 4 : no todas las gráficas planas que requieren 4 colores contienen K 4 . En particular, existe un gráfico plano sin 4 ciclos que no puede ser de 3 colores. [8]
Factorizar a través de un homomorfismo
Una coloración 3 de un gráfico G puede describirse mediante un homomorfismo de gráfico de G a un triángulo K 3 . En el lenguaje de los homomorfismos, el teorema de Grötzsch establece que cada grafo plano sin triángulos tiene un homomorfismo con K 3 . Naserasr demostró que todo gráfico plano sin triángulos también tiene un homomorfismo con el gráfico de Clebsch , un gráfico de 4 cromáticas. Combinando estos dos resultados, se puede demostrar que todo gráfico plano sin triángulos tiene un homomorfismo con un gráfico de tres coloraciones sin triángulos, el producto tensorial de K 3 con el gráfico de Clebsch. La coloración del gráfico puede recuperarse luego 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 se pueda asignar un homomorfismo a cualquier otro gráfico plano sin triángulos. [9]
Representación geométrica
Un resultado de de Castro et al. (2002) combina el teorema de Grötzsch con la conjetura de Scheinerman sobre la representación de gráficos planos como gráficos de intersección de segmentos de línea . Demostraron que todo gráfico plano sin triángulos se puede representar mediante una colección de segmentos de línea, con tres pendientes, 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 3 del gráfico asignando dos vértices del mismo color siempre que sus segmentos de línea tengan la misma pendiente.
Complejidad computacional
Dado un gráfico plano sin triángulos, se puede encontrar un color 3 del gráfico en tiempo lineal . [10]
Notas
- ↑ a b Grünbaum (1963) .
- ^ Thomassen (2003)
- ^ Glebov, Kostochka y Tashkinov (2005) .
- ↑ Asghar (2012)
- ^ Steinberg y Younger (1989)
- ^ Dvořák, Zdeněk ; Kráľ, Daniel; Thomas, Robin (2009), Gráficos sin triángulos de tres colores en superficies V.Coloreando gráficos planos con anomalías distantes , arXiv : 0911.0885 , Bibcode : 2009arXiv0911.0885D.
- ^ "El Premio Europeo de Combinatoria" , EuroComb 2015 , Universidad de Bergen, Septiembre 2015 , recuperada 09/16/2015.
- ^ Heckman (2007) .
- ^ Naserasr (2007) , Teorema 11; Nešetřil y Ossona de Mendez (2012) .
- ^ Dvořák, Kawarabayashi y Thomas (2009) . Para trabajos anteriores sobre algoritmos para este problema, consulte Kowalik (2010) .
Referencias
- Asghar, Nabiha (2012), "Teorema de Grötzsch" (PDF) , Tesis de maestría, Universidad de Waterloo , doi : 10.13140 / RG.2.1.1326.9367.
- Berge, Claude (1960), "Les problèmes de colaration en théorie des graphs", Publ. Inst. Estadístico. Univ. París , 9 : 123-160. Como lo cita Grünbaum (1963) .CS1 maint: posdata ( enlace )
- de Castro, N .; Cobos, FJ; Dana, JC; Márquez, A. (2002), "Gráficos planos sin triángulos como gráficos de intersección de segmentos" (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 7-26, doi : 10.7155 / jgaa.00043 , MR 1898201.
- Dvořák, Zdeněk ; Kawarabayashi, Ken-ichi ; Thomas, Robin (2009), "Gráficos planos sin triángulos de tres colores en tiempo lineal", Proc. 20 de ACM-SIAM Simposio sobre discreto Algoritmos (PDF) , pp 1176-1182,. ArXiv : 1302.5121 , bibcode : 2013arXiv1302.5121D , Archivado desde el original (PDF) en 10/18/2012 , recuperada 02/22/2013.
- Glebov, AN; Kostochka, AV; Tashkinov, VA (2005), "Gráficos planos más pequeños sin triángulos que no se pueden colorear en 3 listas", Matemáticas discretas , 290 (2–3): 269–274, doi : 10.1016 / j.disc.2004.10.015.
- Steinberg, Richard; Younger, DH (1989), "Teorema de Grötzsch para el plano proyectivo", Ars Combinatoria , 28 : 15–31.
- Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120, MR 0116320.
- Grünbaum, Branko (1963), "Teorema de Grötzsch sobre 3 colores", Michigan Math. J. , 10 (3): 303–310, doi : 10.1307 / mmj / 1028998916 , MR 0154274.
- Heckman, Christopher Carl (2007), sobre la marcha de la conjetura de Steinberg , Archivado desde el original en 2012-07-22 , recuperada 2012-07-27.
- Kowalik, Łukasz (2010), "Gráficos planos rápidos sin triángulos de 3 colores" (PDF) , Algorithmica , 58 (3): 770–789, doi : 10.1007 / s00453-009-9295-2.
- Naserasr, Reza (2007), "Homomorfismos y coloraciones de bordes de gráficos planos", Journal of Combinatorial Theory , Serie B, 97 (3): 394–400, doi : 10.1016 / j.jctb.2006.07.001 , MR 2305893.
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "2.5 Homomorphism Dualities", Sparsity , Algorithms and Combinatorics, 28 , Heidelberg: Springer, pp. 15-16, doi : 10.1007 / 978-3-642-27875-4 , hdl : 10338 .dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
- Thomassen, Carsten (2003), "Una prueba de color de lista corta del teorema de Grötzsch", Journal of Combinatorial Theory, Serie B , 88 (1): 189-192, doi : 10.1016 / S0095-8956 (03) 00029-7.