Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp012801pg46x
Title: On Containment Relations in Directed Graphs
Authors: Kim, Ilhee
Advisors: Seymour, Paul D
Contributors: Applied and Computational Mathematics Department
Keywords: coloring
containment relation
digraph
immersion
minor
tournament
Subjects: Mathematics
Computer science
Issue Date: 2013
Publisher: Princeton, NJ : Princeton University
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.
URI: http://arks.princeton.edu/ark:/88435/dsp012801pg46x
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Kim_princeton_0181D_10622.pdf719.31 kBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.