MATHEMATICA BOHEMICA, Vol. 133, No. 1, pp. 85-98 (2008)

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang

Kathy McKeon, Connecticut College, Department of Mathematics, 270 Mohegan Avenue, Box 5561, New London, CT 06320, USA; Garry L. Johns, Saginaw Valley State University, University Center, Department of Mathematical Sciences, MI 48710-0001, USA; Ping Zhang, Gary Chartrand, Western Michigan University, Department of Mathematics, Kalamazoo, MI 49008, USA, e-mail:

Abstract: Let $G$ be a nontrivial connected graph on which is defined a coloring $c E(G) \rightarrow\{1, 2, \ldots, k\}$, $k \in\bbN$, of the edges of $G$, where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ contains a rainbow $u-v$ path for every two vertices $u$ and $v$ of $G$. The minimum $k$ for which there exists such a $k$-edge coloring is the rainbow connection number $\rc(G)$ of $G$. If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u-v$ geodesic, then $G$ is strongly rainbow-connected. The minimum $k$ for which there exists a $k$-edge coloring of $G$ that results in a strongly rainbow-connected graph is called the strong rainbow connection number $\src(G)$ of $G$. Thus $\rc(G) \le\src(G)$ for every nontrivial connected graph $G$. Both $\rc(G)$ and $\src(G)$ are determined for all complete multipartite graphs $G$ as well as other classes of graphs. For every pair $a, b$ of integers with $a \ge3$ and $b \ge(5a-6)/3$, it is shown that there exists a connected graph $G$ such that $\rc(G)=a$ and $\src(G)=b$.

Keywords: edge coloring, rainbow coloring, strong rainbow coloring

Classification (MSC2000): 05C15, 05C38, 05C40

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2008–2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition