The Linkage Problem for Group-labelled Graphs

This 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 $G_1, G_2, \ldots$ of graphs, there exist indices $i < j$ such that $G_i$ is isomorphic to a minor of $G_j$. 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.