Seminář G²OAT: Rainbow Separating Path Systems

Kdy

5. 5. 2025
13:00 – 14:00

Kde

Místnost TH:A-1247

Thákurova 7, Praha 6

V rámci pravidelného pondělního semináře skupiny G²OAT Alexander Clifton představí koncept tzv. duhových separačních systémů cest v grafech, které umožňují odlišit každou dvojici hran pomocí barevně rozlišených cest. Ukáže přesné i asymptoticky nejlepší odhady pro různé třídy grafů, včetně cest, cyklů, pavouků a stromů.

Web akce

Abstrakt

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.

Za obsah stránky zodpovídá: Bc. Veronika Dvořáková