The four color theorem:
is only valid if the graph is planar. I wonder if there is an analogous theorem that can be used without that hypothesis. It's obvious more colors are going to be needed, but I wonder what is the upper bound.
The problem from which the question comes from is that I need to design a voracious algorithm which needs to give color to the nodes of a graph using the least possible colors, in a way that two adjacent nodes cannot have the same color.
The graph can be pretty complex and is (generally) not planar and does not have any particular structure.
The idea is to find a theorem that can limit the number of colors used to make the selection function of the voracious algorithm computationally simple.