Rainbow connection in graphs

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

Mathematica Bohemica, Tome 133 (2008) no. 1, pp. 85-98.

Résumé

Let $G$ be a nontrivial connected graph on which is defined a coloring $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $, $k \in {\mathbb{N}}$, 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 $\mathop {\mathrm 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 $\mathop {\mathrm src}(G)$ of $G$. Thus $\mathop {\mathrm rc}(G) \le \mathop {\mathrm src}(G)$ for every nontrivial connected graph $G$. Both $\mathop {\mathrm rc}(G)$ and $\mathop {\mathrm 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 \ge 3$ and $b \ge (5a-6)/3$, it is shown that there exists a connected graph $G$ such that $\mathop {\mathrm rc}(G)=a$ and $\mathop {\mathrm src}(G)=b$.

Détail

DOI : 10.21136/MB.2008.133947

Classification : 05C15, 05C38, 05C40
Keywords: edge coloring; rainbow coloring; strong rainbow coloring