**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

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

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

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:

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?!

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

–

–

(Y)