coloring. On the other hand, the last two chapters are devoted to interesting varia-
tions of coloring (Ramsey-type colorings) and applications in art-gallery problems.
Preface to the English Edition
This book is an extended and updated translation of a book originally written
in Polish and published in 2002 as "Optymalizacja dyskretna. Modele i metody
kolorowania graf6w". The holder of the copyright, Wydawnictwa Naukowo-Tech-
niczne (Polish Scientific and Technical Publishers) graciously provided the rights to
the English edition pro bono. The authors express their gratitude to the reviewers of
the Polish edition, Professors M. Borowiecki and Z. Lone, for numerous corrections.
The Polish edition has been awarded the prize of the Ministry of National Ed-
ucation. This English edition is the result of several years' effort of young scientists
of three Polish academic centers: Gdansk University of Technology, the University
of Gdansk and the University of Zielona G6ra. All these schools have programs
devoted to algorithmic graph coloring. While Professor Marek Kubale of Gdansk
University of Technology coordinated the entire project, the authors of the chap-
ters were members of his Ph.D. seminar devoted to algorithmic aspects of graph
theory. Some of them now conduct their own research and head their own research
groups elsewhere. The work on this book was partially supported by a number of
grants from the Polish State Committee for Scientific Research. In addition, Robert
Janczewski and Michal Malafiejski were supported by FNP.
Several authors received scientific prizes for the work published in this volume.
After the publication of the Polish original in October 2002, a group of com-
puter scientists and mathematicians from the University of Kentucky (Drs. Jerzy
Jaromczyk, Zbigniew Lone (on leave from Warsaw University of Technology), Vic-
tor Marek and Miroslaw Truszczynski) and the Rochester Institute of Technology
(Dr. Stanislaw Radziszowski) approached the American Mathematical Society on
behalf of the authors of the volume proposing the publication of the English version.
From the beginning the project enjoyed the support of AMS staff: Dr. S. Gelfand
and Ms. Christine Thivierge of the Acquisitions Department. Thanks to the gen-
erosity of the copyright holder (Polish Scientifical and Technical Publishers) this
translation can now be presented to the American reader. The text was translated
by the authors and then revised by the American team.