Skip to main content

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

Time: Mon 2023-08-21 11.00 - 12.00

Location: Cramer room

Respondent: Lindeberg Anna

Supervisor: Marc Hellmuth

Export to calendar


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.