MATH Seminar

Title: Erdos-Pósa property of tripods in directed graphs
Seminar: Discrete Mathematics
Speaker: Meike Hatzel of Institute for Basic Science
Contact: Liana Yepremyan, lyeprem@emory.edu
Date: 2024-10-23 at 4:00PM
Venue: MSC E406
Download Flyer
Abstract: Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A \emph{tripod} in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix. We prove that tripods in directed graphs exhibit the Erd?s-Pósa property. More precisely, there is a function $f\colon $N$ \rightarrow{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$.