very strong result, asserting that every simple graph can be edge-colored with
colors. In other words, this result says that the problem is approximable with an
absolute error guarantee of 1 on simple graphs. The first proof of NP-hardness of
edge-coloring is due to Holyer
Of course, edge-coloring can be regarded as a
special case of vertex-coloring, namely the problem of coloring the vertices of the
corresponding line graph.
Models of graph coloring
For many problems which cannot be easily reduced to classical coloring of the
vertices or edges of an associated graph we introduce more general, nonclassical
models of coloring. In general, the coloring of a graph can consist of assigning
colors to vertices, edges, and faces of a plane graph or any combination of the
above sets simultaneously. Moreover, for each model of coloring we have various
rules on legality or optimality of solutions. Nonclassical models can introduce
additional conditions of the usage of colors by making it possible to use more than
one color per element, permitting the splitting of colors into fractions or admitting
the swathing of colors. In general, there are several dozen graph coloring models
described in the literature
However, only a dozen or so are relevant (from
a practical point of view). These include list coloring, chromatic sum coloring,
equitable coloring, fractional coloring, rank coloring, harmonious coloring, radio-
coloring, interval coloring, circular coloring, strong coloring and path coloring. Most
of them deal with vertex-coloring and edge-coloring, but some of them are defined
only for vertex-coloring (e.g. harmonious) or edge-coloring (e.g. interval). In this
book we consider in detail the models of coloring, which are most useful from a
practical point of view. Those include:
classical coloring,
equitable coloring,
chromatic sum coloring,
rank coloring,
harmonious coloring,
interval coloring,
circular coloring,
path coloring,
list coloring.
The overhelming majority of these models can be regarded as generalizations of
classical graph coloring in the sense that they yield legal colorings.
Individual chapters, devoted to various models, are largely independent of each
other and can be read separately. In each of them we highlight algorithmic aspects,
i.e. the construction of polynomial-time algorithms for graph coloring in the dis-
cussed model. These algorithms are exact if a particular subproblem admits such
a solution or approximate in the general case. The above selection of models is
purposeful. While preparing the selection, potential applications were taken into
account. They include such diverse areas of technology as task scheduling, cellular
telephony, connection networks, radiocommunication, VLSI design and production
systems, etc.
Not only models but also modes are important in algorithmic graph coloring.
Therefore one of the first introductory chapters of this book is devoted to on-line
Previous Page Next Page