Rainbow connection in graphs
 
 
Description:  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 (Maebashi Institute of Technology, Japan), Colton Magnant (Georgia Southern University, GA, USA), Ângela Mestre (CELC, Univ. Lisboa), Manuel Silva (Univ. Nova de Lisboa), and Teresa Sousa (Univ. Nova de Lisboa).

Date:  2013-12-04
Start Time:   15:00
Speaker:  Henry Liu (Univ. Nova de Lisboa)
Institution:  Universidade Nova de Lisboa
Place:  Room 5.5 - DMUC
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support