Combinatorics Seminar

When: Sunday, February 24, 10am Where: Schreiber 309 Speaker: Raphael Yuster, University of Haifa Title: Rainbow connectivity

Abstract:

An edge-colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In addition to being a purely combinatorial problem, rainbow connectivity has several natural applications. In this talk I will survey (and hopefully also prove) several results, and state some open problems concerning rainbow connectivity.

Among the results we will address:

1. The extremal graph-theoretic aspects. In particular, the value of rc(G) as a function of the minimum degree of G.

2. The computational complexity aspects.

3. The rainbow connectivity of the random graph G(n,p).

The results are based on joint works with Y. Caro, A. Lev, Y. Roditty, Z. Tuza and with S. Chakraborty, E. Fischer, A. Matsliah.