A reminder: this is today.
----------------------------------------------------
On 2025-11-23 08:45, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday 27 November, given by Alexander Clifton. Please find the talk details below.
Best regards, Misha Tyomkyn.
Rainbow Separating Path Systems Alexander Clifton The Czech Technical University in Prague
November 27, 2025, 12:20 in S6 Abstract
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
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz