El teorema de los cuatro colores:
sólo es válido si el grafo es planar. Me pregunto si hay un teorema análogo que puede ser utilizado sin necesidad de esa hipótesis. Es obvio que los más colores van a ser necesarios, pero me pregunto ¿cuál es el límite superior.
Información adicional:
El problema de la que surge la pregunta es que necesito para el diseño de un algoritmo voraz que necesita para dar color a los nodos de la gráfica con el mínimo posible de colores, de manera que dos nodos adyacentes no tengan el mismo color.
El gráfico puede ser bastante complejo y es (en general) no es plana y no tiene ninguna estructura en particular.
La idea es encontrar un teorema que puede limitar el número de colores que se utilizan para hacer la función de selección de la voraz algoritmo computacionalmente simple.
