Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp012801pg46x
DC FieldValueLanguage
dc.contributor.authorKim, Ilheeen_US
dc.contributor.otherApplied and Computational Mathematics Departmenten_US
dc.date.accessioned2013-09-16T17:26:31Z-
dc.date.available2013-09-16T17:26:31Z-
dc.date.issued2013en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp012801pg46x-
dc.description.abstractContainment 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.en_US
dc.language.isoenen_US
dc.publisherPrinceton, NJ : Princeton Universityen_US
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the <a href=http://catalog.princeton.edu> library's main catalog </a>en_US
dc.subjectcoloringen_US
dc.subjectcontainment relationen_US
dc.subjectdigraphen_US
dc.subjectimmersionen_US
dc.subjectminoren_US
dc.subjecttournamenten_US
dc.subject.classificationMathematicsen_US
dc.subject.classificationComputer scienceen_US
dc.titleOn Containment Relations in Directed Graphsen_US