Conde Grecha
| Conde Grecha | |
|---|---|
| picos | once |
| costillas | veinte |
| Radio | 2 |
| Diámetro | 2 |
| Circunferencia | cuatro |
| automorfismos | 10 ( D5 ) |
| Número cromático | cuatro |
| índice cromático | 5 |
| Propiedades |
Hamiltoniano sin triángulos |
| Archivos multimedia en Wikimedia Commons | |
El gráfico de Grötzsch es un gráfico libre de triángulos con 11 vértices, 20 aristas, número cromático 4 y número de cruce 5. El gráfico lleva el nombre del matemático alemán Herbert Grötzsch y demuestra la necesidad de la suposición de planaridad en el teorema de Grötzsch ( Grötzsch 1959), que establece que cualquier gráfico plano sin triángulos se puede colorear con 3 colores. El gráfico de Grötzsch es miembro de una secuencia infinita de gráficos sin triángulos, en los que cada gráfico es el mycelskiano del gráfico anterior, a partir del gráfico nulo . Esta secuencia de gráficos fue utilizada por Mycielski ( 1955 ) para mostrar que hay gráficos sin triángulos con un número cromático arbitrariamente grande. Por esta razón, a veces el Conde Gröcz se llama Conde Mycielski o Mycielski-Gröcz. A diferencia de otros gráficos posteriores en la secuencia, el gráfico de Grötsch es el gráfico libre de triángulos más pequeño con su número cromático ( Chvátal 1974 ).
Häggkvist ( Häggkvist 1981 ) usó una versión modificada del grafo de Grötzsch para refutar la conjetura de Erdős y Simonovits ( Erdős, Simonovits 1973 ) sobre el número cromático de los gráficos sin triángulos de mayor grado. La modificación de Heggquist es reemplazar cada uno de los vértices de cinco grados cuatro del gráfico de Grötzsch con tres vértices, y reemplazar cada uno de los vértices de cinco grados tres con dos vértices. Cada uno de los vértices restantes de quinto grado se reemplaza por cuatro vértices. Dos vértices en este gráfico ampliado están conectados por una arista si sus vértices correspondientes estaban conectados por una arista en el gráfico de Groetscha. El resultado es un grafo libre de triángulos regulares de 10 con 29 vértices y número cromático 4, que refuta la hipótesis de que no hay ningún grafo libre de triángulos con número cromático 4 y n vértices en el que cada vértice tenga más de n /3 vecinos.
El gráfico de Grötzsch tiene un índice cromático de 5, un radio de 2, una circunferencia de 4 y un diámetro de 2. También es un gráfico de 3 vértices conectados y de 3 k bordes conectados . El número de independencia del gráfico es 5 y el número de dominancia es 3.
Propiedades algebraicas
El grupo de automorfismos completo del gráfico de Grötzsch es isomorfo al grupo diédrico de décimo orden D 5 , el grupo de simetría de un pentágono regular , incluidas la rotación y la reflexión.
El polinomio característico del gráfico de Grötsch es
Véase también
- Count Khvatala es otro pequeño gráfico de 4 colores sin triángulos.
Literatura
- Chvatal. Gráficos y combinatoria (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). Berlín: Lecture Notes in Mathematics, vol. 406, Springer-Verlag. — S. 243–246 . .
- Sobre un problema de valencia en la teoría de grafos extremos // Matemáticas discretas . - 1973. - V. 5 , núm. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X . .
- Grotzsch. 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. - 1959. - T. 8 . — S. 109–120 . .
- Haggkvist. Ciclos impares de longitud especificada en grafos no bipartitos. — S. 89–99 . .
- Mycielski. Sur le coloriage des graphs // Colloq. Matemáticas.. - 1955. - T. 3 . — S. 161–162 . .
Enlaces
- Weisstein, Eric W. Grötzsch Graph (inglés) en el sitio web de Wolfram MathWorld .