Teorema de los cuatro colores
From Wikipedia, the free encyclopedia
En teoría de grafos, el teorema de los cuatro colores (o teorema de la minimalidad cromática) ye un teorema sobre la coloración de grafos qu'establez lo siguiente:
|
Dando por fechu que les rexones axacentes comparten non solo un puntu, sinón tou un segmentu de cantu (frontera) de mancomún.
Trés colores son abondos pa mapes simples, pero en dellos casos ye necesariu un cuartu color adicional, esto ye, cuando una rexón a colorear queda zarrada por un númberu impar de rexones que se toquen formando un ciclu. El teorema de los cinco colores, que la so demostración ye curtia y elemental, establez que cinco colores son abondos pa colorear un mapa y foi probáu nel sieglu XIX por Heawood.[1] Una serie de pruebes falses y falsos contraejemplos apaecieron dende'l primer enunciáu del teorema de los cuatro colores en 1852.
El problema del mapa de cuatro colores foi plantegáu, per primer vegada, pol estudiante Francis Guthrie en 1852, lo que foi comunicáu a Augustus de Morgan.[2] La conxetura fíxose famosa cola declaración d'Arthur Cayley, en 1878, nel sentíu de que la encetara. Foi resueltu, a mediaos de 1970, por Kenneth Appel y Wolfgang Haken.[3]