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 in 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_k(G) denote the minimum size of a rainbow separating path system with k colors. While c_k(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_2(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_2(T) is at most (4n+2)/3, which is asymptotically best possible. For more colors, we establish bounds for several graph classes including trees and random graphs.

Joint work with George Kontogeorgiou, S Taruni, and Ana Trujillo-Negrete