Physical Sciences and Mathematics Commons^™

Computing Minimum Rainbow And Strong Rainbow Colorings Of Block Graphs, Melissa Karanen, Juho Lauri

Michigan Tech Publications

A path in an edge-colored graph G is rainbow if no two edges of it are colored the same. The graph G is rainbow-connected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph G is strongly rainbow-connected. The minimum number of colors needed to make G rainbow-connected is known as the rainbow connection number of G, and is denoted by src(G). Similarly, the minimum number of colors needed to make G strongly rainbow-connected is known as the strong rainbow connection number of G, and …