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)\le 4n/3\), which is asymptotically best possible. Additionally, we show that \(c_k(T)\le n\) for \(k\ge 4\), but that this does not hold for \(k=3\).

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