Preface

Optimization problems can be naturally divided into two categories: continuous

and discrete. Continuous optimization problems are those that allow continuous

variables. Generally speaking the aim of such problems is to find a set of real

numbers or a real function, which optimize a certain criterion. On the other hand,

discrete optimization problems are those that contain discrete variables. The aim of

such problems is to find a combinatorial object, which optimizes a certain criterion

function in a finite space of legal solutions. On the whole, each of these two types

of problems requires separate solution techniques. This book is devoted to selected

problems of combinatorial optimization, otherwise known as discrete optimization.

The fact that such combinatorial calculations are becoming increasingly important

stimulates research and development of the field. Common programmers' expe-

rience shows that the number of combinatorial computations appearing in user

programs increases more rapidly than the number of numerical computations. The

reason for this is that besides the traditional fields of applications of mathematics

in engineering and physics, discrete structures appear now more frequently than

continuous ones. Discrete optimization is a branch of applied mathematics and

theoretical computer science that includes various topics of graph theory, network

design, mathematical programming, sequencing and scheduling, as well as many

others. One of its areas is graph coloring, to which this book is entirely devoted.

Graph coloring

Graph coloring is one of the oldest and best-known problems of graph theory.

As people became accustomed to applying the tools of graph theory to the solu-

tion of real-world technological and organizational problems, new chromatic models

emerged as a natural way of tackling many practical situations. Internet statistics

show that graph coloring is one of the central issues in the collection of several

hundred classical combinatorial problems

[60].

The reason for this is the simplicity

of its formulation and seemingly natural solution on the one hand, and numerous

potential applications on the other. Unfortunately, high computational complexity

prevents the efficient solution of numerous problems by means of graph coloring.

For example, the deceptively simple task of deciding if the chromatic number of

a graph, i.e. the smallest number of colors that can be assigned to the vertices of

a graph so that no pair of adjacent vertices is colored with the same color, is at

most 3 remains NP-complete

[194].

In practice this means that our task cannot be

solved in polynomial time and, consequently, it is impossible to find a chromatic

solution to a graph on several dozens of vertices in a reasonable time. Needless

to say, graphs of this size are definitely too small to be considered satisfactory in

practical applications.

ix