Rainbow path separation systems (RPSS)

Abstract: A family of paths P in a graph G is (k,t)-rainbow separating if it can be coloured with k colours such that for every t-tuple of edges e_1, …, e_t there exist t paths P_1, …, P_t of distinct colours such that P_i contains the edge e_i and does not contain any other edge of the t-tuple. Much work has been done on (∞,2)-RPSS, also known as strong path separation systems. In this talk I will present some optimal results on (2,2)-RPSS, together with a more general treatise on (k,2)-RPSS for all values of k.

Posted on Nov 28, 2024 in Seminario de Grafos, Seminars