Graph colouring problem: 6 and 5 colouring theorems and algorithms

Question

I'm a Computer Science student and as an extra assignment from my professor, I had to prove the 6 and 5 - colouring theorems and to write algorithms (in C++) for both. I managed to prove both of the theorems and to write a code for a 6 - colouring. The idea for the 6 - colouring is the following:

Step 1: Color 1st vertex with 1st color.

Step 2: For all it's neighbors, pick the 1st unused colored among it's neighbors (the neighbors of the chosen neighbor, I hope I made that clear) and color it with it. Do this for all verices.

Now the 5 - colour theorem: Every planar graph is 5-colorable (a planar graph is a graph in which no two edges intersect).

My professor told me that this doesn't apply for a 5 - colouring, due to the fact that each vertex can has 5 neighbors which use the 5 given colors and told me to go for something else.

Can anyone help me with an algorithm for 5 - colouring problem? Maybe an implementation?

Answer 1

I had to prove the 6 and 5 - colouring theorems and to write algorithms (in C++) for both. I managed to prove both of the theorems

Since the theorems are proved, required colorings exist. Thus a brute-force algorithm that checks all $6^n$ ($5^n$) possible colorings of the graph vertices into $6$ ($5$) colors will always find it. It even suffices to check only $4^n$ possible colorings of the graph vertices into $4$ colors, because by The Four Color theorem there exists a required coloring into $4$ colors. But I guess that if we’ll do this then your professor will say that we are cheaters. :-) The key here is that the constructive proofs produce much more fast algorithms than the brute force check.

Your six coloring algorithm will stop if it will encounter a vertex of high degree, which has the neighbors already colored into each of six colors. To fix this we need to color the vertices in some order, constructed as follows. Find a vertex of degree less than $6$ (the Euler formula should imply existence of such a vertex, and this is the key which makes $6$ a magic number :-) ). This vertex will be colored the last. Now remove this vertex from the graph and it the remaining graph find a vertex of degree less than $6$. This vertex will be colored previous to the last. Now remove this vertex from graph and so on.

The $5$-color case is essentially more complicated than $6$-color. A short inductive and illustrated proof of Thomassen theorem stating that each planar graph is even $5$-list colorable is presented in Lecture 10 “Planar Graphs” of a block-course “Algorithmic Graph Theory” by Dr. Joachim Spoerhase and Prof. Dr. Alexander Wolff. I recommend your to start to read this presentation from page 215.

Answer 2

How did you prove the theorems? The proofs I know are constructive - they give a nice recursive way to generate the colorings.

6-color theorem: There must exist a vertex of degree $5$ or less, remove it and recursively $6$ color the reduced graph, then add the vertex back in, using a color different than its neighbors.

5-color theorem: Essentially the same as the 6-color theorem, except with an extra protocol if all five colors are represented amongst the neighbors. In that case, you should swap the color of a neighbor not in a Kempe chain to the neighbor of the updated color.