Proper
coloring of a simple, symmetric and connected graph is a classical
problem that deals with m-colorability optimization problem.
The problem asks for the smallest integer m, for which the
graph G = (V, E) with vertex set V and edge set E can be colored
properly. This minimum integer is called the chromatic number
X(G). A k-vertex coloring of any graph G is an assignment
of k-colors 1,2,3,..., k to the vertices of G.
The
reasons for the importance of the graph coloring problem are
twofold. First, there are several areas of practical interest
in which the ability to color an undirected graph with the
smallest number of colors has direct influence on how efficiently
a certain target problem can be solved. Such areas include
timetable scheduling (Wood, 1969), examination scheduling
(Leighton, 1979), register allocation (Chow and Hennessy,
1984), printed circuit testing (Garey et al., 1976), electronic
bandwidth allocation (Gamst, 1986), microcode optimization
(Micheli, 1994), channel routing (Sarma et al., 1985), the
design and operation of flexible manufacturing systems (Stecke,
1985), computation of sparse Jacobian elements by finite differencing
in mathematical programming (Coleman and More, 1983), etc.
The
other reason is: the graph coloring problem has been shown
to be computationally hard at a variety of levels - not only
its decision problem variant is NP-complete (Garey and Johnson,
1979), but also its approximate version is NP-hard (Baase
and Gelder, 1999). |
