6
$\begingroup$

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.

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – jgon Apr 29 '15 at 19:41
  • 1
    $\begingroup$ 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?) $\endgroup$ – Tryss Apr 29 '15 at 19:44
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Brooks theorem seems to be what I need. Also, I appreciate the link to the greedy coloring algorithm page. I didn't know the exact English name for that type of algorithm. $\endgroup$ – D1X Apr 30 '15 at 9:10
1
$\begingroup$

Since $K_n$, the complete graph on $n$ vertices, has chromatic number $n$, we can have nonplanar graphs with arbitrary chromatic number.

However, there are theorems for graphs which can be embedded on other surfaces with no edge crossings. In particular, it happens that you can colour a torus with 7 colours, and in general, this page provides a general form of the result which you might find interesting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.