gráfico de error
En el campo matemático de la teoría de grafos , el grafo de Errera es un grafo de 17 vértices y 45 aristas . Alfred Errera lo publicó en 1921 como un contraejemplo a la prueba errónea de Kempe del teorema de los cuatro colores ; [1] [2] fue nombrado después de Errera por Hutchinson & Wagon (1998) . [1]
El grafo de Errera es plano y tiene número cromático 4, índice cromático 6, radio 3, diámetro 4 y perímetro 3. Todos sus vértices son de grado 5 o 6 y es un grafo conexo por 5 vértices y por 5 aristas. gráfico _
El grafo de Errera no es un grafo transitivo de vértice y su grupo de automorfismos completo es isomorfo al grupo diédrico de orden 20, el grupo de simetrías de un decágono , que incluye rotaciones y reflexiones.
El polinomio característico del grafo de Errera es .
El teorema de los cuatro colores establece que los vértices de cada gráfico plano se pueden colorear con cuatro colores, de modo que no hay dos vértices adyacentes que tengan los mismos colores. Alfred Kempe publicó una prueba errónea en 1879 , pero se descubrió que era errónea en 1890. El teorema de los cuatro colores no recibió una prueba válida hasta 1976. La prueba de Kempe se puede traducir a un algoritmo para colorear gráficos planos, que también es erróneo. Se encontraron contraejemplos de su prueba en 1890 y 1896 (el gráfico de Poussin ), y más tarde, el gráfico de Fritsch y el gráfico de Soifer proporcionaron dos contraejemplos más pequeños. [3]Sin embargo, hasta el trabajo de Errera, estos contraejemplos no mostraban que todo el algoritmo de coloreado fallara. Más bien, asumieron que todos los vértices del gráfico, excepto uno, ya habían sido coloreados y demostraron que el método de Kempe (que supuestamente modificaría el coloreado para extenderlo a todos los gráficos) falló en esos casos precoloreados. El gráfico de Errera, por otro lado, proporciona un contraejemplo de todo el método de Kempe. Cuando este método se ejecuta en el grafo de Errera, comenzando sin vértices coloreados, puede fallar en encontrar un coloreado válido para todo el grafo. [1] Además, a diferencia del grafo de Poussin, todos los vértices del grafo de Errera tienen grado cinco o más. Por lo tanto, en este gráfico, es imposible evitar los casos problemáticos del método de Kempe eligiendo vértices de menor grado.
