Society for Industrial and Applied Mathematics, 1999, -214 pp.
Intersection graphs provide theory to underlie much of graph theory. They epitomize graph-theoretic structure and have their own distinctive concepts and emphasis. They subsume concepts as standard as line graphs and as nonstandard as tolerance graphs. They have real applications to topics like biology, computing, matrix analysis, and statistics (with many of these applications not well known).
While there are other books covering various topics of intersection graph theory, these books have focus and intent that are different from ours. Even those that are out of date are still valuable sources that we urge our readers to consult further. [Golumbic, 1980], with its partial updating in [Golumbic, 1984], remains a standard, excellent source, organized around perfect graphs. There is much related content in [Roberts, 1976, 1978b], both of which emphasize intersection graphs and applications. Among others, [Berge, 1989] develops many of the general concepts in terms of hypergraphs, [Fishbu, 1985] and [Trotter, 1992] stress an order-theoretic viewpoint, [Kloks, 1994] emphasizes tree width, and [Prisner, 1995] focuses on graph operators. [Mahadev & Peled, 1995] is devoted to threshold graphs. [Brandstadt, 1993] and [Brandstadt, Le & Spinrad, to appear] discuss many of the relevant graph classes. [Zykov, 1987] includes valuable references to the Russian literature up to that date.
We have tried to write a concise book, packed with content. The first four chapters focus on what we feel are the most developed topics of intersection graph theory, emphasizing chordal, interval, and competition graphs and their underlying common theory; Chapter 5 discusses the allied topic of threshold graphs. Chapter 6 extends the common theory to p-intersection, multigraphs, and tolerance. Chapter 7 adopts a different spirit, serving as a guide to an active, scattered literature; we hope it communicates the flavor of various topics of intersection graph theory by offering tastes of enough different topics to lure interested readers into pursuing the citations and leaing more. We have pointed in a multitude of directions, while resisting trying to point in all directions.
We have made the book self-contained modulo the basics present in any introductory graph theory text, whether one like [Chartrand & Lesniak, 1996] with virtually no overlap with our topics, or one like [West, 1996] that introduces several of the same topics. We hope it can serve as a platform from which one can launch more detailed investigations of the broad array of topics that involve intersection graphs. The more than one hundred simple exercises scattered throughout the first six chapters are meant to be done as they occur, to reinforce and extend the discussion.
In spite of its size, the Bibliography does not pretend to be complete. Many relevant papers are not included—even some of our own—partly by design and partly reflecting our ignorance and prejudices. We hope that even connoisseurs will find a few surprises, though. We have made a special effort to include early papers and recent papers with good bibliographies, but we have typically included very few papers that emphasize solving particular problems (e.g., coloring, domination, identifying max cliques, and a host of others) or that emphasize details of algorithms and complexity. Papers marked as "to appear" had not been published when this book was completed and should be looked for using the American Mathematical Society's MathSciNet. We also intend limited updating (including, inevitably, corrections) on a website locatable though the authors' home institutions.
The following are among the possible uses of this book: (i) as a source book for mathematical scientists and others who are not familiar with this material; (ii) as a guide for a research seminar, utilizing the references to explore additional topics in depth; (iii) as a 5-6 week "unit" in an advanced undergraduate/graduate level course in graph theory.
Intersection Graphs.
Chordal Graphs.
Interval Graphs.
Competition Graphs.
Threshold Graphs.
Other Kinds of Intersection.
Guide to Related Topics.
Intersection graphs provide theory to underlie much of graph theory. They epitomize graph-theoretic structure and have their own distinctive concepts and emphasis. They subsume concepts as standard as line graphs and as nonstandard as tolerance graphs. They have real applications to topics like biology, computing, matrix analysis, and statistics (with many of these applications not well known).
While there are other books covering various topics of intersection graph theory, these books have focus and intent that are different from ours. Even those that are out of date are still valuable sources that we urge our readers to consult further. [Golumbic, 1980], with its partial updating in [Golumbic, 1984], remains a standard, excellent source, organized around perfect graphs. There is much related content in [Roberts, 1976, 1978b], both of which emphasize intersection graphs and applications. Among others, [Berge, 1989] develops many of the general concepts in terms of hypergraphs, [Fishbu, 1985] and [Trotter, 1992] stress an order-theoretic viewpoint, [Kloks, 1994] emphasizes tree width, and [Prisner, 1995] focuses on graph operators. [Mahadev & Peled, 1995] is devoted to threshold graphs. [Brandstadt, 1993] and [Brandstadt, Le & Spinrad, to appear] discuss many of the relevant graph classes. [Zykov, 1987] includes valuable references to the Russian literature up to that date.
We have tried to write a concise book, packed with content. The first four chapters focus on what we feel are the most developed topics of intersection graph theory, emphasizing chordal, interval, and competition graphs and their underlying common theory; Chapter 5 discusses the allied topic of threshold graphs. Chapter 6 extends the common theory to p-intersection, multigraphs, and tolerance. Chapter 7 adopts a different spirit, serving as a guide to an active, scattered literature; we hope it communicates the flavor of various topics of intersection graph theory by offering tastes of enough different topics to lure interested readers into pursuing the citations and leaing more. We have pointed in a multitude of directions, while resisting trying to point in all directions.
We have made the book self-contained modulo the basics present in any introductory graph theory text, whether one like [Chartrand & Lesniak, 1996] with virtually no overlap with our topics, or one like [West, 1996] that introduces several of the same topics. We hope it can serve as a platform from which one can launch more detailed investigations of the broad array of topics that involve intersection graphs. The more than one hundred simple exercises scattered throughout the first six chapters are meant to be done as they occur, to reinforce and extend the discussion.
In spite of its size, the Bibliography does not pretend to be complete. Many relevant papers are not included—even some of our own—partly by design and partly reflecting our ignorance and prejudices. We hope that even connoisseurs will find a few surprises, though. We have made a special effort to include early papers and recent papers with good bibliographies, but we have typically included very few papers that emphasize solving particular problems (e.g., coloring, domination, identifying max cliques, and a host of others) or that emphasize details of algorithms and complexity. Papers marked as "to appear" had not been published when this book was completed and should be looked for using the American Mathematical Society's MathSciNet. We also intend limited updating (including, inevitably, corrections) on a website locatable though the authors' home institutions.
The following are among the possible uses of this book: (i) as a source book for mathematical scientists and others who are not familiar with this material; (ii) as a guide for a research seminar, utilizing the references to explore additional topics in depth; (iii) as a 5-6 week "unit" in an advanced undergraduate/graduate level course in graph theory.
Intersection Graphs.
Chordal Graphs.
Interval Graphs.
Competition Graphs.
Threshold Graphs.
Other Kinds of Intersection.
Guide to Related Topics.