En el campo matemático de la teoría de grafos , el grafo de Grötzsch es un grafo libre de 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 de que los grafos libres de triángulos planos son 3-coloreables. [1]
El grafo de Grötzsch es un miembro de una secuencia infinita de grafos sin triángulos, cada uno de ellos 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, el grafo de Grötzsch a veces también se denomina 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 diedro D 5 de orden 10, el grupo de simetrías de un pentágono regular , incluyendo 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]
Aunque no es un grafo plano , puede incrustarse en el plano proyectivo sin cruces. Esta incrustación tiene diez caras, todas ellas cuadriláteros. [4]
La existencia del grafo de Grötzsch demuestra que el supuesto de planaridad es necesario en el teorema de Grötzsch de que todo grafo planar sin triángulos es 3-coloreable. [1] Tiene circunferencia impar cinco pero circunferencia cuatro, y no tiene ningún homomorfismo de grafo con un grafo cuya circunferencia sea cinco o más, por lo que forma un ejemplo que distingue la circunferencia impar de la circunferencia máxima que se puede obtener a partir 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 con 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, reemplazar cada uno de los cinco vértices de grado tres del grafo de Grötzsch por un conjunto de dos vértices y reemplazar el vértice de grado cinco restante del grafo de Grötzsch 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 regular libre de 10 triángulos con 29 vértices y número cromático 4, lo que refuta la conjetura de que no existe ningún grafo libre de 4 triángulos cromáticos en el que cada vértice tenga más de 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 de distancia con 16 vértices y 40 aristas: tanto el grafo de Grötzsch como el grafo de Clebsch son libres de triángulos y cuatricromá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 cada grafo libre de triángulos y cuatricromático es asimismo un subgrafo inducido del grafo de Clebsch que a su vez contiene al grafo de Grötzsch como un subgrafo inducido. [8] El grafo de Chvátal es otro pequeño grafo cuatricromático sin 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.
