TY - JOUR
T1 - Rainbow connection for some families of hypergraphs
AU - Silva, Manuel Almeida
AU - Sousa, Teresa Maria Jerónimo
AU - Liu, Henry Chung Hang
PY - 2014/1/1
Y1 - 2014/1/1
N2 - An edge-coloured path in a graph is rainbow if its edges have distinct colours. The rainbow connection number of a connected graph G, denoted by rc(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path. The function rc(G) was first introduced by Chartrand et al. [Math. Bohem., 133 (2008), pp. 85-98], and has since attracted considerable interest. In this paper, we introduce two extensions of the rainbow connection number to hypergraphs. We study these two extensions of the rainbow connection number in minimally connected hypergraphs, hypergraph cycles and complete multipartite hypergraphs.
AB - An edge-coloured path in a graph is rainbow if its edges have distinct colours. The rainbow connection number of a connected graph G, denoted by rc(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path. The function rc(G) was first introduced by Chartrand et al. [Math. Bohem., 133 (2008), pp. 85-98], and has since attracted considerable interest. In this paper, we introduce two extensions of the rainbow connection number to hypergraphs. We study these two extensions of the rainbow connection number in minimally connected hypergraphs, hypergraph cycles and complete multipartite hypergraphs.
KW - rainbow connection number
KW - hypergraph colouring
KW - Graph colouring
U2 - 10.1016/j.disc.2014.03.013
DO - 10.1016/j.disc.2014.03.013
M3 - Article
SN - 0012-365X
VL - 327
SP - 40
EP - 50
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - NA
ER -