Description: A known problem in graph theory , Graph coloring is defined as coloring the nodes of a graph with the minimum number of colors without any two adjacent nodes having the same color.
The problem consists of an undirected graph G=(V,E) is a map c: V -> S such that c(u) != c(v) whenever there exists an edge (u,v) in G.
(where ā€œSā€ is a finite set of colors.)

The problem is to determine the minimum cardinality (the number of colors) of S for a given graph G or to ask whether it is able to color graph G with a certain number of colors. For example, how many color do we need to color the United States on a map in such a way that adjacent states have different color?

However, coloring a general graph with the minimum number of colors (the cardinality of set S) is known to be an NP-complete problem. One often relies on heuristics to find a solution. A widely-used general greedy based approach is starting from an ordered vertex enumeration V1, ..., Vn of G, to assign Vi to the smallest possible color for i from 1 to n.

Applications: estimation of sparse Jacobins,scheduling, registering allocation, optimization and parallel numerical computation.
external image bgc.jpg

Algorithmic problem:
Input - a graph (V,E),C
V - set of Vertices
E - set of Edges <= VxV
c - set of Colors

Output - boolean - can he graph be colored following the rules using the set of colors?
True or False

Algorithmic Solution:
(1) In case you would like to dermine if a graph can be colored with 2 colors, you are actually asking yourself whether the graph is bipartite, and thus polynomial time-computable.

(2) Brute force for |S| = k colors considers every of the (n over k) assignments of colors to vertices and checks for each if it is legal.


(3) Greedy algorithm , This technique focuses on carefully picking the next vertex to be colored. In this heuristic algorithm, once a vertex is colored, its color never changes.

Heuristics:
When using a Greedy algorithm one need to define the method of picking the next vertex, In this case the Heuristic is the way of picking the next vertex:

1) First Fit
2) Degree based ordering

Reference: New Graph Coloring Algorithms by Dr. Hussein Al-Omari and Khair Eddin Sabri