Technical

Graph Coloring



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 Algorithm:

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

Advertisements

One thought on “Graph Coloring

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s