We investigate the application of intersection graphs to subalgebras of an algebara. Specifically, we define the intersection graph of a semigroup S to be the graph G(S) whose vertex set consists of all proper subsemigroups of S.

The vertices X and Y are adjacent in G(S) if and only if X and Y have a nonempty intersection. The structure of G(S) is examined. We also discuss the characterization of those semigroups whose intersection graph is a certain class of graphs.

A graph G=(V,E) is called a trapezoid graph if there are two parallel lines (called baselines) so that for each vertex x in V, there is a trapezoid T(x) with bases on the two baselines with the property that x is adjacent to y if and only if T(x) and T(y) intersect. A trapezoid graph is called a parallelogram or triangle graph if we can assign trapezoids that are parallelograms or triangles, respectively (so that x and y are adjacent if and only if T(x) and T(y) intersect). A trapezoid, parallelogram, or triangle graph is called proper if we can assign trapezoids, parallelograms or triangles, respectively, so that no one is a subset of any other. A trapezoid, parallelogram or triangle graph is called unit if we can assign trapezoids, parallelograms or triangles, respectively, so that all have unit area. As in the case of interval graphs, the unit graphs are proper. It is straightforward to show that triangle graphs are all proper triangle graphs. We now have 8 graph properties, Trap, Par, Tri, UTrap, UTri, Upar, PTrap, Ppar. Of the 256 subsets of these properties, it is possible to find 20 that describe classes of graphs (e.g. parallelogram and proper trapezoid) that are not obviously equal to classes described by other subsets. There are examples to show that all 20 of these classes are different; we shall discuss some of them.

Each of these classes has a transitive orientation given in a natural way by the assignment of trapezoids, parallelograms, or triangles. It seems likely that every orientation can be described by such an assignment, but except for trapezoid graphs, parallelogram graphs, proper trapezoid graphs, and unit parallelogram graphs, and triangle graphs, I am not aware of any proofs. This might make a good topic for joint work in the workshop.

Interval graphs and probe interval graphs were introduced for studies in certain biological fields specializing in genetics in the late 50's (for interval graphs), and in the late 90's (for probe interval graphs). The definition of a probe interval graph is conducive to a natural extension called interval bigraphs. This extension distinguishes a new class of interval graphs exhibiting ties to R/L-interval bigraphs which were introduced in a non-biological context. Classes of R/L-interval bigraphs can be generated by interval graphs and probe interval graphs. Well-known characterizations of interval graphs and probe interval graphs will be reviewed. Interval bigraphs will be introduced and characterized. R/L-interval bigraphs will be characterized. Also containment relationships between these classes of graphs in the bipartite case will be proven.

Motivated by high-dimensional classification, we investigate a class cover problem with an associated family of directed graphs - class cover catch digraphs (CCCD). CCCDs are a special case of catch digraphs. In order to solve the underlying class cover problem, we are interested in determining the domination number of any given CCCD. We have calculated the exact distribution of the domination number of CCCD generated from a random one dimensional process. A characterization of CCCDs is also given.

In an odd-intersection representation of a graph, each vertex, v, has a finite set of labels associated with it, S(v), so that a pair of vertices {u,v}, is an edge in the graph if and only if the size of the intersection of the sets of labels, S(u) and S(v), is odd. The odd-intersection number of a graph is the least number of labels used in an odd-intersection representation. Various results are given, including a comparison between the odd-intersection number of a graph and the rank of its adjacency matrix.

A robust, flexible method for solving the archaeology seriation problem of Sir Flinders Petrie using a genetic algorithm(GA) approach will be discussed.

In this talk, we will report on several improvements on coloring tolerance graphs and on some shortest path problems which are generalized from known results on interval graphs. We will also discuss some results on bipartite tolerance graphs and algorithmic questions that we have been investigating.

An interval order representation has intervals [g_1(x),g_2(x)] assigned to elements (vertices) such that x < y iff g_2(x) < g_1(y) (the graph is the co-comparability graph of the order). A split interval order (equivalent to a unit bitolerance order) has 3 points g_1(x) < g_2(x) < g_3(x) assigned to elements such that x < y iff g_3(x) < g_2(y) and g_2(x) < g_1(y). We can extend this an arbitrary number, k, of splitting points. This gives another notion of dimension for orders. We discuss basic results on these sorts of orders and graphs. Note that another intersection perspective on these structures is to consider k levels and look at intersections of staircases with vertical risers and varying length treads.

A graph G = (V,E) is a path tolerance graph with tolerance t (PT(t)-graph) provided there is a map v --> P[v] from the vertex set V of G into subpaths of a tree T such that vertices v and w are adjacent in G iff the representing paths P[v] and P[w] have at least t nodes in common. The tree T is called the host tree for the PT(t)-representation. A graph G is a path tolerance graph (PT-graph) iff G is a PT(t)-graph for some tolerance t.

Previously studied classes of path tolerance graphs include the PT(1)-graphs, known as either path graphs or VPT graphs (for vertex intersection graphs of paths in a tree). The PT(1)-graphs form a class intermediate between interval graphs (where the host is a path) and chordal graphs. PT(1)-graphs can be recognized in polynomial time. Around 1985, several papers by Golumbic and Jamison, Syslo, and Tarjan also studied the class of PT(2)-graphs, known as EPT-graphs (for edge intersection graphs of paths in a tree). The recognition problem for EPT-graphs is NP-complete -- in fact, recognizing which VPT-graphs are EPT-graphs is NP-complete.

This talk will show how the recognition problem for general PT-graphs reduces to an integer programming problem and hence is at least decidable. Some of the structure of general PT-graphs will also be discussed and several constructions for graphs that are not PT(t) for any tolerance t will be given.

Let D be a digraph. The competition graph of D has the same set of vertices as D and an edge between vertices u and v if and only if there is a vertex x in D such that (u,x) and (v,x) are arcs of D. We call vertex x a prey of vertex v if (v,x) is an arc of D. Then the competition graph of a digraph D can be rephrased as the intersection graph of the family each member of which is the set of prey of a vertex of D. The competition number of a graph G, denoted by k(G), is the smallest number k such that G together with k isolated vertices is the competition graph of an acyclic digraph. Roberts [1978] showed that the competition number of a chordal graph is less than or equal to one and it seems natural to ask about the competition number of a graph having exactly one hole (a hole is a chordless cycle of length at least 4). In this talk, we present the result showing that the competition number of such a graph G is less than or equal to two, and give conditions under which the competition number of G is less than or equal to one. We also show that if G is a connected graph with at least one pendant vertex and G' is obtained from G by deleting some pendant vertices of G, then k(G) = k(G').

Key words: competition graph, competition number, chordal graph, chordless cycle.

Building on the concepts of trapezoid graphs and triangle graphs discussed in Ken's talk, I generalize somewhat further to (n,i,f)-tube graphs. Consider a "tube" of n parallel lines in n-dimensional space, and otherwise in general position. In the same way that we fit trapezoids and triangles between two parallel lines in the plane, we can fit n-dimensional polytopes between the n parallel lines in n-space. We call a graph an (n,i,f)-tube graph if it is the intersection graph of a set of these n-dimensional polytopes, such that each polytope has exactly n+i vertices on the lines and exactly f vertices in the interior of the tube (and no vertices outside the tube).

We call the set of all (n,i,f)-tube graphs T(n,i,f). I have been interested in the containment relations between these sets, and I have a number of results and many, many open questions.

This research is motivated by a paper of Habib, Kelly, and Mohring. In this paper, the authors prove that every result about (n,i,f)-tube graphs extends to the analagously defined (n,i,f)-tube orders.

It is well known that chordal graphs are intersection graphs of subtrees of a tree . It is also known that chordal graphs have perfect elimination orderings. We will discuss some perfect elimination orderings of chordal graphs.

The Sphere-of-Influence graph (SIG) of a set of at least two points in the plane is the intersection graph of a set of open balls centered at the points in the set. The radius of the ball centered at point P is the shortest distance from P to the other points in the set. Alternatively, the radius of the ball at P is the largest number so that the open ball centered at P contains no other point from the set. For a complete SIG, think of the balls as having to be close enough so that each pair of balls overlaps yet far enough apart so that no center lies inside more than one ball. Phrased that way, the maximum complete SIG determines an invariant of the euclidean plane. It is easy to find sets of eight points that have a complete SIG. It is known that no set of twelve points has a complete SIG. We provide lots of evidence that no set of nine points has a complete SIG.

Tolerance graphs and interval probe graphs are two generalizations of the well known class of interval graphs. All three families are defined in terms of being able to assign an interval on the line to each vertex of the graph such that there is an edge between two vertices if and only if the intersection of their intervals is non-empty and satisfies an "extra" condition. For interval graphs, there is no extra condition. For probe graphs, the vertices are partitioned into two sets P (probes) and N (non-probes), and the extra condition is that at least one of the two vertices of an edge must be in P. For tolerance graphs, the vertices are assigned positive real numbers (tolerances), and the extra condition is the requirement that the size of the intersection of the two intervals must be greater than or equal to the minimum of the two tolerances in order to produce an edge. It is known, and easy to show, that every interval graph is a probe graph (by choosing N to be empty), and that every probe graph is a tolerance graph (by assigning infinite tolerance to each member of N and a small tolerance to each member of P.) Moreover, for all three models, we can place additional restrictions of requiring that all intervals be of unit length or that no interval properly contains another. Clearly, a unit interval representation is also a proper representation. Conversely, however, it is well known that unit tolerance graphs do not equal proper tolerance graphs, but unit interval graphs do equal proper interval graphs. In this talk, we present the complete hierarchy of all nine subclasses taken from {} x {} together with examples separating different classes. Thus, we survey these which are known and prove those which are new. We also introduce the family of chordal probe graphs, and discuss some of their properties, issues of recognition and characterization. We also prove that the enhancement of a chordal probe graph (with respect to a given partition into probes and nonprobes) is a chordal graph. This is a generalization of a similar result of P. Zhang for interval probe graphs. Finally, we also present the new result that the graph sandwich problem for probe graphs is NP-complete.

Circular-arc graphs are natural analogs of chordal (and interval) graphs, but without some of the features that make chordal/interval graphs particularly nice; perhaps the biggest difference is the failure of the Helly condition.

Suppose you restrict circular-arc representations so as to have no three or fewer arcs cover the entire circle and to have the endpoints of arcs be distinguishable by other arcs. Such 'restricted circular-arc graphs' now enjoy many of the nice features of chordal graphs, including the Helly condition, and their theory is surprisingly parallel to that of chordal graphs when 'clique cycles' are substituted for clique trees. Restricted circular-arc graphs also have distinctive features, such as the following characterization:

(1) There are no simplicial vertices.

(2) The only induced wheels are K_4s.

(3) The number of vertices, minus the number of edges, plus the number of triangles, minus the number of K_4s, and so on, equals zero.

The lack of simplicial vertices in particular shows that, in other ways, we have gotten far away from chordal/interval graphs, and that their potential applicability can be expected to be in rather different directions from chordal/interval graphs.

A cheap recursive formula for enumerating isomorphism classes of rooted trees.

Analysis of the normal structure of those p-groups that are the automorphism groups of finite trees.

A verbal characterization of tree automorphism groups, along with a bijection between tree automorphism groups and their associated words.

A computationally cheap scheme for identifying a given rooted tree with a canonical word, affording cheap computation of:

• whether two given trees are isomorphic.
• the automorphism group of a given tree.

We define and discuss a relatively new type of proximity graph and mention some open problems.

Interval graphs may be described in terms of thee different models. First, they are the intersection graphs of intervals on the real line (or equivalently: of subpaths of a very long path). Second, a graph is an interval graph if and only if it does not contain a forbidden subgraph from a list of specified graphs. Third, a graph is an interval graph if and only if we can eliminate its vertices one by one such that in each step a vertex of a specified type is eliminated.

This lecture will explore these three models "Intersection Graph", "Forbidden Subgraph", "Elimination Scheme" for chordal graphs and tolerance graphs. The presentation will mostly be elementary, but already at this level applications and challenging puzzles arise.

The concept of interval graph was introduced by the Hungarian mathematician Hajos in connection with a scheduling problem and independently by the Nobel-prize-winning geneticist Seymour Benzer in connection with the problem of understanding the makeup of the fine structure inside the gene. Since then, this one simple idea has had applications in archaeology, developmental psychology, utility theory in economics, traffic light phasing, ecology, and many other areas, and has given rise to some fascinating mathematical theories and algorithms. This talk will introduce the concept of interval graph.

A probe interval graph is an variation of interval graph that arose from the DNA physical mapping of molecular biology. Given a graph, and a partition of its vertex set into probe vertices and non-probe vertices, the graph is called a partitioned probe interval graph if an interval can be assigned to each vertex such that two vertices are adjacent if and only if their corresponding intervals have a nonempty intersection, and at least one of the interval is a probe vertex. Unit probe interval graph is a special case of probe interval graph where we require that all the intervals assigned to the vertices must have the same length. We give a characterization for a cycle free graph to be a unit probe interval graph using a list of forbidden subgraphs.

Sen, Das, Roy, and West introduced the class of interval digraphs as a directed analogue of the well-known interval graph. A digraph is an interval digraph if each vertex can be assigned a closed source interval and a closed sink interval so that there is an edge from vertex u to vertex v if and only if the source interval for u intersects the sink interval for v. Bogart and Trenk provide a different directed graph analogue based on the work of tolerance graphs. A directed graph is a bounded bitolerance digraph if each vertex v can be assigned a real closed interval I(v) = [L(v), R(v)], and left and right tolerance points, p(v) and q(v) respectively, in I(v) so that there is an edge from vertex u to vertex v if and only if L(u) <= q(v) and R(u) >= p(v). Note that according to this definition, bounded bitolerance digraphs have a loop at each vertex. For convenience, the definition is sometimes phrased to specifically exclude loops.

The class of interval digraphs and class of bounded bitolerance digraphs are both properly contained in the class of digraphs of Ferrers dimension at most two. In this paper we explore the structure and relationships between these and related digraph classes. We show that the class of interval digraphs with a loop at each vertex is a proper subset of the class of bounded bitolerance digraphs.

In this all-institute talk we introduce tolerance graphs as a generalization of interval graphs. Special classes of tolerance graphs arise in different applications. For example, unit tolerance graphs (like unit interval graphs) will have a representation using intervals that all have the same length, and these classes can arise in the problem of assigning rooms to one hour classes when only a limited number of rooms is available.

We discuss a hierarchy of classes of tolerance graphs and prove some of the classes are equal using geometric arguments. The ordered sets perspective is useful in analyzing these classes.