Heuristics for the Generalized Graph Coloring Problem

In this paper, we propose heuristics for the
$(k, i){-}$
coloring problem, which is a generalization of classical graph coloring problem. We also explore an application of
$(k, i)$
-coloring problem to coding theory. In an undirected graph, a proper
$(k, i)$
-coloring is an assignment of a set of
$k$
colors to each vertex such that any pair of adjacent vertices share at most
$i$
colors. The
$(k, i){-}$
chromatic number of the graph is the minimum number of colors required to properly
$(k, i)$
-coloring the graph. The
$(k, i){-}$
coloring problem asks to compute the
$(k, i)$
-chromatic number of the graph. The
$(k, i)$
-coloring problem is a generalization of the classical graph coloring problem. The
$(k, i)$
-coloring problem is NP-Hard. As polynomial time algorithms unlikely for NP-Hard problems, approximation algorithms or heuristics produce quality solution on many real world instances. The classical graph coloring problem is well studied in many dimensions. Many heuristics and meta-heuristics have been proposed for the classical coloring problem. Here the question is can we generalize these heuristics and meta heuristics for the
$(k, i)$
-coloring problem. In this paper, we propose generalized greedy heuristic and simulated annealing based heuristic for the
$(k, i)$
-coloring problem. The weight of a binary vector is the number of 1 ‘s in the vector. The hamming distance between two binary vectors is the number of bits they differ. A constant weight binary code is a set of binary vectors of length
$n$
, weight
$w$
and with a pairwise hamming distance of at least
$d$
. The maximum possible number of constant weight binary codes of length
$n$
, weight
$w$
and with hamming distance at least
$d$
is denoted by
$A(n, d, w)$
. There is a connection to
$(k, i)$
-coloring and constant weight binary codes. In this paper, we make an attempt to explore this connection.