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.
Additional information:
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.
Best Answer
Unless you have some structure to your graph, I guess the best you can do is use Brooks' theorem.
It states that every graph except the complete graph and cycle graph can be colored with $\Delta$ colors, the maximum degree.
But if you want to use a voracious algorithm, i.e. always take the first color available, you might need up to $\Delta + 1$ colors. This will always be enough however. The wikipedia page on the greedy coloring algorithm might interest you.