Topics in Intersection Graph Theory
Published on 28. February 1999
Book
Paperback/Softback
213 pages
978-0-89871-430-2 (ISBN)
Description
Finally there is a book that presents real applications of graph theory in a unified format. This book is the only source for an extended, concentrated focus on the theory and techniques common to various types of intersection graphs. It is a concise treatment of the aspects of intersection graphs that interconnect many standard concepts and form the foundation of a surprising array of applications to biology, computing, psychology, matrices, and statistics.
The authors emphasize the underlying tools and techniques and demonstrate how this approach constitutes a definite theory within graph theory. Some of the applications are not widely known or available in the graph theoretic literature and are presented here for the first time. The book also includes a detailed literature guide for many specialized and related areas, a current bibliography, and more than 100 exercises.
The authors emphasize the underlying tools and techniques and demonstrate how this approach constitutes a definite theory within graph theory. Some of the applications are not widely known or available in the graph theoretic literature and are presented here for the first time. The book also includes a detailed literature guide for many specialized and related areas, a current bibliography, and more than 100 exercises.
More details
Series
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Product notice
Paperback (trade)
Unsewn / adhesive bound
Dimensions
Height: 228 mm
Width: 152 mm
Thickness: 11 mm
Weight
386 gr
ISBN-13
978-0-89871-430-2 (9780898714302)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
Preface
Chapter 1: Intersection Graphs. Basic Concepts
Intersection Classes
Parsimonious Set Representations
Clique Graphs
Line Graphs
Hypergraphs
Chapter 2: Chordal Graphs. Chordal Graphs as Intersection Graphs
Other Characterizations
Tree Hypergraphs
Some Applications of Chordal Graphs
Split Graphs
Chapter 3: Interval Graphs. Definitions and Characterizations
Interval Hypergraphs
Proper Interval Graphs
Some Applications of Interval Graphs
Chapter 4: Competition Graphs. Neighborhood Graphs
Competition Graphs
Interval Competition Graphs
Upper Bound Graphs
Chapter 5: Threshold Graphs. Definitions and Characterizations
Threshold Graphs as Intersection Graphs
Difference Graphs and Ferrers Digraphs
Some Applications of Threshold Graphs
Chapter 6: Other Kinds of Intersection. p-Intersection Graphs
Intersection Multigraphs and Pseudographs
Tolerance Intersection Graphs
Chapter 7: Guide to Related Topics. Assorted Geometric Intersection Graphs
Bipartite Intersection Graphs, Intersection Digraphs, and Catch (Di)Graphs
Chordal Bipartite and Weakly Chordal Graphs
Circle Graphs and Permutation Graphs
Clique Graphs of Chordal Graphs and Clique-Helly Graphs
Containment, Comparability, Cocomparability, and Asteroidal Triple-Free Graphs
Infinite Intersection Graphs
Miscellaneous Topics
P4-Free Chordal Graphs and Cographs
Powers of Intersection Graphs
Sphere-of-Influence Graphs
Strongly Chordal Graphs
Bibliography
Index.
Chapter 1: Intersection Graphs. Basic Concepts
Intersection Classes
Parsimonious Set Representations
Clique Graphs
Line Graphs
Hypergraphs
Chapter 2: Chordal Graphs. Chordal Graphs as Intersection Graphs
Other Characterizations
Tree Hypergraphs
Some Applications of Chordal Graphs
Split Graphs
Chapter 3: Interval Graphs. Definitions and Characterizations
Interval Hypergraphs
Proper Interval Graphs
Some Applications of Interval Graphs
Chapter 4: Competition Graphs. Neighborhood Graphs
Competition Graphs
Interval Competition Graphs
Upper Bound Graphs
Chapter 5: Threshold Graphs. Definitions and Characterizations
Threshold Graphs as Intersection Graphs
Difference Graphs and Ferrers Digraphs
Some Applications of Threshold Graphs
Chapter 6: Other Kinds of Intersection. p-Intersection Graphs
Intersection Multigraphs and Pseudographs
Tolerance Intersection Graphs
Chapter 7: Guide to Related Topics. Assorted Geometric Intersection Graphs
Bipartite Intersection Graphs, Intersection Digraphs, and Catch (Di)Graphs
Chordal Bipartite and Weakly Chordal Graphs
Circle Graphs and Permutation Graphs
Clique Graphs of Chordal Graphs and Clique-Helly Graphs
Containment, Comparability, Cocomparability, and Asteroidal Triple-Free Graphs
Infinite Intersection Graphs
Miscellaneous Topics
P4-Free Chordal Graphs and Cographs
Powers of Intersection Graphs
Sphere-of-Influence Graphs
Strongly Chordal Graphs
Bibliography
Index.