Introduction and Definition
Hmmmm, do you love colors?! Seems interesting! Yes it is! Graph coloring is one of the most interesting topics in the graph theory, here’s a simplified problem definition for graph coloring:
Graph coloring is to give each node a color such that no two adjacent nodes have the same color.
It seems easy from the first look, “why not to give each node a unique color?!” … seems okay, but the real challenge appears when we say
Give each node a color such that no two adjacent nodes have the same color using the minimum number of colors. This is the real challenge!
–
Applications – Map Coloring
One of the most interesting applications on the graph coloring is to color a map; giving each region a color such that no to adjacent regions -having a common side- have the same color. We can translate the map into a graph by representing each region by a node, and making an edge between two nodes if the two regions having a common side.
Here’s an example:
Given this map of A, B, C, D, E and F regions:
We can translate it to be a graph as the following:
We can now apply a graph coloring algorithm:
So, we can color our map only using four colors, here it is:
It’s nice to know that, there is a theorem called Four Color Theorem states that:
Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
Here’s an example of a map-coloring to the states of United States
.
It shows clearly that the minimum number of used colors is four.
–
Other Applications
There are many other applications on graph coloring like:
- Suduko generator, we can simply generate suduko boards by representing each cell as a node and link nodes in the same row and the same column and the same inner square, here’s an example of what cell (1,1) should be linked with
- Scheduling events
Scheduling events that have common participants to find the minimum number of time slots to hold these events is a problem that can be solved graph coloring by representing each event by a node and link two nodes if they have common participant.
–
Algorithms
Greedy graph coloring is very simple, it starts with any node, flooding from this node and giving each reached vertex the first available color, here the availability means that there’s no adjacent node has the color.
Here’s a trace for the greedy algorithm applied to the above example:
| Starting with node (A) giving it blue color. |  |
| Go to node (B) and give it a new color –green– because it is adjacent to node (A) which has blue color. |  |
| Now, go to node (C) and also give it a new color – red-. |  |
| Coloring node (E) with the first available color in the used colors list, we’ll pick up the blue. |  |
| Now (D), picking the first available color –green-. |  |
| Coloring (F) with a new color –yellow– because its adjacent nodes has all the used colors. |  |
Greedy algorithm is not the only one existed for solving the graph coloring problem; it’s good also to read about DOM algorithm
–
Do you know?!
Do you know that graph coloring is an NP complete problem; this means that no polynomial-time algorithm is found till now to solve this problem optimally. Do you know also that finding a solution for one of the NP Complete problems qualifies you to win the Nobel Prize! WOW! Why not to think about that : D
–
–
Amr Abdulrahman 
(Y)