Gráfico de Grötzsch

En el campo matemático de la teoría de grafos , el grafo de Grötzsch es un grafo sin triángulos con 11 vértices, 20 aristas, número cromático 4 y número de cruces 5. Recibe su nombre del matemático alemán Herbert Grötzsch , quien lo utilizó como ejemplo en relación con su teorema de 1959 que establece que los grafos planares sin triángulos son 3-coloreables. ^{[ 1 ]}

El grafo de Grötzsch pertenece a una secuencia infinita de grafos sin triángulos, cada uno de los cuales es el mycielskiano del grafo anterior en la secuencia, comenzando desde el grafo de una arista; esta secuencia de grafos fue construida por Mycielski (1955) para demostrar que existen grafos sin triángulos con un número cromático arbitrariamente grande. Por lo tanto, al grafo de Grötzsch también se le denomina a veces grafo de Mycielski o grafo de Mycielski-Grötzsch. A diferencia de los grafos posteriores en esta secuencia, el grafo de Grötzsch es el grafo sin triángulos más pequeño con su número cromático. ^{[ 2 ]}

El grupo de automorfismos completo del grafo de Grötzsch es isomorfo al grupo diedral D ₅ de orden 10, el grupo de simetrías de un pentágono regular , que incluye tanto rotaciones como reflexiones. ^{[ 3 ]} Estas simetrías tienen tres órbitas de vértices: el vértice de grado 5 (por sí mismo), sus cinco vecinos y sus cinco no vecinos. De manera similar, hay tres órbitas de aristas, que se distinguen por su distancia al vértice de grado 5.

El polinomio característico del grafo de Grötzsch es ^{[ 3 ].}$${\displaystyle (x-1)^{5}(x^{2}-x-10)(x^{2}+3x+1)^{2}.}$$

Aunque no es un grafo planar , puede incrustarse en el plano proyectivo sin cruces. Esta incrustación tiene diez caras, todas las cuales son cuadriláteros. ^{[ 4 ]} El grafo es 1-planar .

La existencia del grafo de Grötzsch demuestra que la suposición de planaridad es necesaria en el teorema de Grötzsch que afirma que todo grafo planar libre de triángulos es 3-coloreable. ^{[ 1 ]} Tiene circunferencia impar cinco pero circunferencia cuatro, y no tiene ningún homomorfismo de grafos con una circunferencia de cinco o más, por lo que constituye un ejemplo que distingue la circunferencia impar de la circunferencia máxima que se puede obtener de un homomorfismo. ^{[ 5 ]}

Häggkvist (1981) utilizó una versión modificada del grafo de Grötzsch para refutar una conjetura de Paul Erdős y Miklos Simonovits ( 1973 ) sobre el número cromático de grafos sin triángulos de alto grado. La modificación de Häggkvist consiste en reemplazar cada uno de los cinco vértices de grado cuatro del grafo de Grötzsch por un conjunto de tres vértices, cada uno de los cinco vértices de grado tres por un conjunto de dos vértices, y el vértice restante de grado cinco por un conjunto de cuatro vértices. Dos vértices en este grafo expandido están conectados por una arista si corresponden a vértices conectados por una arista en el grafo de Grötzsch. El resultado de la construcción de Häggkvist es un grafo libre de triángulos 10- regular con 29 vértices y número cromático 4, lo que refuta la conjetura de que no existe un grafo libre de triángulos 4-cromático. ${\displaystyle n}$-grafo de vértices en el que cada vértice tiene más de${\displaystyle n/3}$vecinos. ^{[ 6 ]} Cada uno de estos grafos contiene el grafo de Grötzsch como un subgrafo inducido . ^{[ 7 ]}

El grafo de Grötzsch comparte varias propiedades con el grafo de Clebsch , un grafo transitivo en distancia con 16 vértices y 40 aristas: tanto el grafo de Grötzsch como el de Clebsch son libres de triángulos y cuatro cromáticos, y ninguno de ellos tiene caminos inducidos de seis vértices . Estas propiedades son casi suficientes para caracterizar estos grafos: el grafo de Grötzsch es un subgrafo inducido del grafo de Clebsch, y todo grafo libre de triángulos y cuatro cromáticos${\displaystyle P_{6}}$El grafo libre de triángulos es asimismo un subgrafo inducido del grafo de Clebsch que, a su vez, contiene el grafo de Grötzsch como subgrafo inducido. ^{[ 8 ]} El grafo de Chvátal es otro pequeño grafo 4-cromático libre de triángulos. Sin embargo, a diferencia del grafo de Grötzsch y del grafo de Clebsch, el grafo de Chvátal tiene un camino inducido de seis vértices.

• Brandt, Stephan (1999), "Sobre la estructura de grafos densos libres de triángulos", Combinatorics, Probability and Computing , 8 (3): 237– 245, doi : 10.1017/S0963548399003831 , MR 1702550 , S2CID 120967754  
• Chvátal, Vašek (1974), "La minimalidad del grafo de Mycielski", Grafos y combinatoria (Actas de la Conferencia Capital, Universidad George Washington, Washington, DC, 1973) , Berlín: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, pp. 243–246 , MR 0360330  
• Erdős, P. ; Simonovits, M. (1973), "Sobre un problema de valencia en la teoría extremal de grafos", Matemáticas Discretas , 5 (4): 323– 334, doi : 10.1016/0012-365X(73)90126-X , MR 0342429 
• Galluccio, Anna; Goddyn, Luis A.; Hell, Pavol (2001), "Los grafos de alta circunferencia que evitan un menor son casi bipartitos", Journal of Combinatorial Theory , Serie B, 83 (1): 1– 14, doi : 10.1006/jctb.2000.2009 , MR 1855793 
• 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, SEÑOR 0116320 
• Häggkvist, R. (1981), "Ciclos impares de longitud especificada en grafos no bipartitos", Teoría de grafos (Cambridge, 1981) , págs. 89–99 , MR 0671908  
• Joyner, W. David; Melles, Caroline Grant (2017), "5.12 Grötzsch graph", Adventures in Graph Theory , Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, Cham, pp. 229–231 , doi : 10.1007/978-3-319-68383-6 , ISBN  978-3-319-68381-2, MR 3753658 
• Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Matemáticas. , 3 (2): 161– 162, doi : 10.4064/cm-3-2-161-162 , SEÑOR 0069494 
• Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), "Tricolorabilidad y subgrafos prohibidos. II. Algoritmos polinomiales", Matemáticas Discretas , 251 ( 1–3 ): 137–153 , doi : 10.1016/S0012-365X(01)00335-1 , MR 1904597 
• Youngs, DA (1996), "Grafos proyectivos 4-cromáticos", Journal of Graph Theory , 21 (2): 219– 227, doi : 10.1002/(SICI)1097-0118(199602)21:2 < 219::AID-JGT12 > 3.0.CO ; 2-E , MR 1368748 

• Weisstein, Eric W. , "Gráfico de Grötzsch" , MathWorld