# Any equivalent to the Four color theorem for non-planar graphs?

The four color theorem:

http://en.wikipedia.org/wiki/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.

• Well if you have a complete graph than you need as many colors as you have vertices, so you would need some other restriction to do anything. What do you have in mind? – jgon Apr 29 '15 at 19:41
• Yes, there is analogous theorems for non planar graphs. I've seen a result like this for graphs on a torus for exemple (don't know how to call them, plannar graphs on a torus?) – Tryss Apr 29 '15 at 19:44

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.
Since $K_n$, the complete graph on $n$ vertices, has chromatic number $n$, we can have nonplanar graphs with arbitrary chromatic number.