Implementation of Algorithms for L(2,1)-Coloring Problems

Graph coloring problems are widely used to study and model the different real time applications. Many real time applications such as Job scheduling, Aircraft scheduling, By processor tasks, region identification use the concept of graph coloring. An L(2, 1)-coloring of a graph G is a function f from vertex set V(G) to the set of all non-negative integers such that the following two conditions are satisfied, i) vertical bar(x) - g(x)vertical bar >= > 2 if d(x, y) = 1 ii) vertical bar f (x) - g(x)vertical bar >= 1 if d(x, y) = 2 where d(x, y) is the distance between two vertices x and y of the graph. The L(2, 1)-coloring number also called as Chromatic number lambda(G) of graph G is the smallest number k such that G has an L(2, 1)-coloring with maxf (v) : v is an element of V (G) = k. In this paper, four algorithms are proposed for finding the exact and another four for the approximate values of lambda(G). The algorithms are compared based on their running time and optimality of the solution for many special types of graphs like general graphs, bipartite graphs and sparse graphs.