Algebra and Logic Seminar - 4/6/2014

Wednesday, 4 June 2014, 2:00 p.m.

Lecturer:  Henry Liu (CMA/FCT-UNL) 

Title: "Rainbow Connection in Graphs"

Local: Room 1.4, Edifício VII
Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: For a connected graph G, the rainbow connection number rc(G) is the minimum number of colours required to colour the edges of G so that, any two vertices are connected by a "rainbow" path (i.e., using distinct colours). The function rc(G) was introduced by Chartrand, Johns, McKeon and Zhang in 2008, and has since attracted considerable interest.

In this talk, we consider generalisations and different versions of the function rc(G). For example, if G is k-connected, then we can generalise rc(G) to the rainbow k-connection number rc_k(G), which is the minimum number of colours required to colour the edges of G so that, any two vertices are connected by k internally vertex-disjoint rainbow paths. On the other hand, a different version of rc(G) considers vertex-colourings. Many results and open problems will be presented. 

Based on a combination of joint works with Rui Carpentier (Universidade de Cabo Verde, Republic of Cape Verde), Shinya Fujita (Yokohama City University, Japan), Colton Magnant (Georgia Southern University, GA, USA), Angela Mestre (CELC-UL), Manuel Silva (CMA-FCT-UNL), and Teresa Sousa (CMA-FCT-UNL).