Rainbow connection in graphs

Chartrand, Gary, et al. "Rainbow connection in graphs." Mathematica Bohemica 133.1 (2008): 85-98. <http://eudml.org/doc/32579>.

@article{Chartrand2008,
abstract = {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 \{r\}c\}(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 \{s\}rc\}(G)$ of $G$. Thus $\mathop \{\mathrm \{r\}c\}(G) \le \mathop \{\mathrm \{s\}rc\}(G)$ for every nontrivial connected graph $G$. Both $\mathop \{\mathrm \{r\}c\}(G)$ and $\mathop \{\mathrm \{s\}rc\}(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 \{r\}c\}(G)=a$ and $\mathop \{\mathrm \{s\}rc\}(G)=b$.},
author = {Chartrand, Gary, Johns, Garry L., McKeon, Kathleen A., Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {edge coloring; rainbow coloring; strong rainbow coloring; edge coloring; rainbow path; rainbow coloring; strong rainbow coloring; rainbow connection number; strong rainbow connection number},
language = {eng},
number = {1},
pages = {85-98},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Rainbow connection in graphs},
url = {http://eudml.org/doc/32579},
volume = {133},
year = {2008},
}

TY - JOUR
AU - Chartrand, Gary
AU - Johns, Garry L.
AU - McKeon, Kathleen A.
AU - Zhang, Ping
TI - Rainbow connection in graphs
JO - Mathematica Bohemica
PY - 2008
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 133
IS - 1
SP - 85
EP - 98
AB - 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 {r}c}(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 {s}rc}(G)$ of $G$. Thus $\mathop {\mathrm {r}c}(G) \le \mathop {\mathrm {s}rc}(G)$ for every nontrivial connected graph $G$. Both $\mathop {\mathrm {r}c}(G)$ and $\mathop {\mathrm {s}rc}(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 {r}c}(G)=a$ and $\mathop {\mathrm {s}rc}(G)=b$.
LA - eng
KW - edge coloring; rainbow coloring; strong rainbow coloring; edge coloring; rainbow path; rainbow coloring; strong rainbow coloring; rainbow connection number; strong rainbow connection number
UR - http://eudml.org/doc/32579
ER -