Diferencia entre revisiones de «Coloración de grafos»

Los primeros resultados sobre coloración de grafos trataban exclusivamente sobre grafos planares en forma de coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, [[Francis Guthrie]] postulopostuló la [[conjetura de los 4 colores]], notando que 4 colores son suficientes para colorear el mapa tal que regiones que comparten un borde común no reciban el mismo color. El hermano de Guthrie pasa el problema a su profesor de matemáticas [[Augustus de Morgan]] en la universidad, mencionado en una carta a William Hamilton en 1852. [[Arthur Cayley]] envía el problema a la [[London Mathematical Society]] en 1879. algunos años después, [[Alfred Kempe]] publicopublicó un paper que resolvía el problema y por una década el problema de los 4 colores se consideró resuelto. Por su contribución Kempe fue elegido Fellow de la [[Royal Society]] y posteriormente presidente de la London Mathematical Society.

En 1890, Heawood descubrió que el argumento de Kempe contenía un error, en ese paper él probó el teorema de los 5 colores, diciendo que cada mapa plano puede ser coloreado con, a loslo más 5 colores, usando ideas de Kempe. En el siguiente siglo, teorías fueron desarrolladas para reducir el número de colores a cuatro, hasta que el teorema de los 4 colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken.