Anna Lindeberg: The Structure of Primitive Edge-Colored Graphs: A Galled Tree Perspective

Abstract.

A galled tree is a rooted, directed, and acyclic graph such that no two ‘undirected’ cycles in it share an edge. A complete edge-colored graph Σ is explained by a labeled galled tree (N, t) if the vertices of Σ are the leaves of N , and t assigns a label to each vertex of N in such a way that the label of the least common ancestor of any two leaves x and y equals the edge-color of the edge {x, y} in Σ. In this thesis we characterize which complete edge-colored graphs of a particular type (so-called primitive edge-colored graphs) can be explained by a galled tree. Furthermore, we investigate when such a galled tree is uniquely determined.