PREFACE

xi

very strong result, asserting that every simple graph can be edge-colored with

~

+

1

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

[166].

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

[183].

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,

• T-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