Research in graph theory and its applications has increased considerably in recent years. Typically, the elaboration of new theoretical structures has motivated a search for new algorithms compatible with those structures. Rather than the arduous and systematic study of every new concept definable with a graph, the main task for the mathematician is to eliminate the often arbitrary and cumbersome definitions, keeping only the "deep"
mathematical problems.
This book, by Martin Golumbic, is intended as an introduction to graph theory through just these practical problems, nearly all of them related to the structure of permutation graphs, interval graphs, circle graphs, threshold graphs, perfect graphs, and others.
The reader will not find motivations drawn from number theory, as is usual for most of the extremal graph problems, or from such refinements of old riddles as the four-color problem and the Hamiltonian tour. Instead, Golumbic has selected practical problems that occur in operations research, scheduling, econometrics, and even genetics or ecology.