Graph Coloring Problem

Graph :-  Its a order pair G(V,E) where V is the set of vertices and E is the set of edges joining some of those those vertices. Thus a graph G(V,E)  where V = {v | v is a vertex of G} and E = {(u,v) | u,v ∈ V}. 

Graph Coloring :- 

           Vertex Coloring :- Find a vector F = (f_v) ,where f_v is called the color of vertex v, such that  f_v ≠ f_u  if (u,v) ∈ E .
           
           Edge Coloring: Find a vector F = (f_e) , where f_e is called the color of edge e, such that f_e ≠ f_g if there is a common vertex u in terminals ( end points of an edge is called terminal . A terminal is one of those pair of vertices which form that edge. ) of e and g.

Algorithm :- 
                Frequency Exhaustive :- Choose an order of the vertices and color them one by one following that order. While coloring vertex v choose the minimum color that satisfy all constraints with so far colored vertices.

In this strategy we will put color 0 to v₁ and minimum color that satisfy constraints with v₁ to v₂ and and minimum color that satisfy constraints with v₁ and v₂ to v₃ so on ...  

              Requirement Exhaustive :- Choose an order of the vertices. Choose color 0 and following the order color those vertices with color 0 which can take this color with satisfying constraints with so far colored vertices. Now go to color 1 and do the same and so on...

This Graph coloring problem has enormous application in networking. Specially in networking we have to allocate channels or frequency to the Mobile Stations ( Mobile, Notebooks etc ) where channel assignment is reduced to a graph coloring problem.