Implementation of algorithms for L(2,1)-coloring problems
Satyanarayana Vollala, S. Indrajeet, Amit D. Joshi, P. S. Tamizharasan, Jobin Jose · 2017
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). |f(x) - g(x)| ≥ 2 if d(x, y) = 1 ii). |f(x) - g(x)| ≥ 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 λ(G) of graph G is the smallest number k such that G has an L(2, 1)-coloring with max f(v): v ϵ V(G) = k. In this paper, four algorithms are proposed for finding the exact and another four for the approximate values of λ(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.