Abstract
dc:description.abstractThis thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled from $\Gamma$, and is thus a generalization of a signed graph. Our primary result is a generalization of the main result from Graph Minors XIII. For any finite abelian group $\Gamma$, and any fixed $\Gamma$-labelled graph $H$, we present a polynomial-time algorithm that determines if an input $\Gamma$-labelled graph $G$ has an $H$-minor. The correctness of our algorithm relies on much of the machinery developed throughout the graph minors papers. We therefore hope it can serve as a reasonable introduction to the subject. Remarkably, Robertson and Seymour also prove that for any sequence G1, G2, \dots of graphs, there exist indices $i<j$ such that Gi is isomorphic to a minor of Gj. Geelen, Gerards and Whittle recently announced a proof of the analogous result for $\Gamma$-labelled graphs, for $\Gamma$ finite abelian. Together with the main result of this thesis, this implies that membership in any minor closed class of $\Gamma$-labelled graphs can be decided in polynomial-time. This also has some implications for well-quasi-ordering certain classes of matroids, which we discuss.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Huynh, Tony
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/4716