We introduce a rainbow variant of separating path systems. For up to four colors, we investigate the minimum size of such a separating system for various graph classes such as paths, cycles, and trees. Furthermore, we analyze the behavior for any number of colors, establishing bounds for a wide class including complete graphs and Erdős-Rényi random graphs.

We prove that for any two graphs G and H , the edges of G can be strongly separated by a collection of linearly many subdivisions of H and single edges. This confirms a conjecture of Botler and Naia.

Abstract. We show that if [Formula: see text] is an [Formula: see text]-vertex digraph with more than [Formula: see text] arcs that does not contain any of three forbidden digraphs, then [Formula: see text] contains every antidirected tree on [Formula: see text] arcs. The forbidden digraphs are those orientations of [Formula: see text] where each of the vertices in the class of size two has either out-degree 0 or in-degree 0. This proves a conjecture of Addario-Berry et al. for a broad class of digraphs, and generalizes a result for [Formula: see text]-free graphs by Balasubramanian and Dobson. We also show that every digraph [Formula: see text] on [Formula: see text] vertices with more than [Formula: see text] arcs contains every antidirected [Formula: see text]-arc caterpillar, thus solving the above conjecture for caterpillars. This generalizes a result of Perles.