On Containment Relations in Directed Graphs

Abstract

Containment relations in graphs such as induced subgraphs, minors, or immersions can be naturally extended to the world of directed graphs. In this thesis, we present new results on several containment relations in digraphs.

The first result is on butterfly minors. It is a containment relation in digraphs which can be considered as an extension of the minor relation in graphs. To obtain a butterfly minor, we may contract edges that do not yield "new" directed cycles. This relation was first introduced in [12]. We prove that the class of all semi-complete digraphs is well-quasi-ordered under this containment relation.

The second result is on strong minors. It is another containment relation in digraphs which also can be considered as an extension of the minor relation in graphs. To obtain a strong minor, we may contract a strongly-connected subdigraph to a vertex. We prove that the class of all semi-complete digraphs is well-quasi-ordered under this containment relation. We also prove that the same wqo statements fail to hold for some slightly larger classes of digraphs containing all semi-complete digraphs.

The third result is on immersions. A digraph is immersed in another if the vertices of the first digraph are mapped to vertices of the second, and edges of the first to directed paths of the second, joining the corresponding pairs of vertices and pairwise edge-disjoint. For digraphs, determining if a fixed digraph can be immersed in an input digraph is a hard problem in general. However, for some small fixed digraphs, we can test this in polynominal time. We prove the existence of such algorithms.

The fourth result is on subtournaments. A set of tournaments T is said to be heroic if every tournament, not containing any member of T as a subtournament, has bounded chromatic number. (The chromatic number of a tournament is the smallest number of colors needed to color the vertices of the tournament so that there is no monochromatic cyclic triangle.) In particular, if a heroic set has size one, then the element of the set is called a hero. In [1], the authors were able to construct all heroes. Here, we present some results on general heroic sets.