Intersection Graphs: Structure and Invariants.

Abstract

Chapter I introduces the definitions of intersection graphs and a number of restrictions of that concept, particularly interval graphs, multiple interval graphs, n-dimensional interval graphs and circular-arc graphs, and reviews the known results concerning them. In Chapter II, a general method for computing intersection numbers is developed. Variations on the intersection number involving order conditions on the label set are introduced, and the case of linear order is fully developed. Chapter III takes up interval graphs and presents a new structural characterization. Also investigated is the structure of interval graphs having representations consisting only of infinite intervals. The study of various generalizations of interval graphs occupies Chapter IV. Interval digraphs are defined and characterized both structurally and in terms of forbidden subdigraphs. A simple recognition algorithm for interval digraphs is presented. Interval networks are also investigated, as well as various other types of intersection digraphs. Circular-arc graphs are characterized structurally, by generalizing the work of Chapter III for interval graphs, and a complete set of forbidden subgraphs is obtained. Circular-arc digraphs are also defined and characterized. For multiple interval graphs, relations between the interval number and structure of a graph are considered. Multiple unit-interval graphs are defined and the unit-interval number is determined for every graph. Multiple arc graphs and arc numbers are also considered, and relationships are developed between the arc number and interval number of a graph. Chapter V takes up the study of the intersection graphs of families of various types of plane sets. A complete characterization is given in the case of families of chords of a circle. Also investigated are families of line segments, families of Jordan arcs, and families of convex regions. Some relations are established among the corresponding classes of graphs, and the chapter closes with two conjectures. In Chapter VI, the notion of a bipartite intersection graph is introduced, in which the family of subsets is partitioned into two classes and only those intersections between classes are used to define adjacency. Natural examples of this type of graph are provided by the incidence graphs of block designs and geometric configurations. These are studied and used to catalog the small self-dual configurations. Bipartite interval graphs are also defined and characterized, and chordal bipartite graphs are shown to be just bipartite subtree graphs. Directed and mixed intersection graphs are also defined and characterized. The final chapter discusses briefly some of the various intersection graphs which can be associated with a given graph. It also comments on potential applications, both within and outside of mathematics, of the various concepts introduced in the preceding chapters.