Alexander Clifton: Rainbow Separating Path Systems скачать в хорошем качестве

Alexander Clifton: Rainbow Separating Path Systems

We define a rainbow separating path system of a graph G as a collection of paths, where for each pair of edges e,f ∈ E(G), there exists a path that contains e but not f, and a path of a different color that contains f but not e. Let cₖ(G) denote the minimum size of a rainbow separating path system with k colors. While cₖ(G) can be bounded in terms of the existing notions of weak and strong separation numbers, we show that it is not a straightforward function of these quantities. We compute c₂(G) exactly when G is a path or cycle, and up to an additive constant when G is a spider. For trees T on n vertices, we apply these results to show that c₂(T) ≤ 4n/3, which is asymptotically best possible. Additionally, we show that cₖ(T) ≤ n for k ≥ 4, but that this does not hold for k=3. Joint work with George Kontogeorgiou, S Taruni, and Ana Trujillo-Negrete.