# Rainbow connection in graphs

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

Mathematica Bohemica (2008)

- Volume: 133, Issue: 1, page 85-98
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topChartrand, 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 -

## References

top- Introduction to Graph Theory, McGraw-Hill, Boston, 2005. (2005)

## Citations in EuDML Documents

top- Futaba Fujie-Okamoto, Kyle Kolasinski, Jianwei Lin, Ping Zhang, Vertex rainbow colorings of graphs
- Xueliang Li, Yongtang Shi, On the Rainbow Vertex-Connection
- Lily Chen, Xueliang Li, Kang Yang, Yan Zhao, The 3-Rainbow Index of a Graph
- Xueliang Li, Mengmeng Liu, Ingo Schiermeyer, Rainbow Connection Number of Dense Graphs
- Arnfried Kemnitz, Ingo Schiermeyer, Graphs with rainbow connection number two
- Arnfried Kemnitz, Jakub Przybyło, Ingo Schiermeyer, Mariusz Woźniak, Rainbow Connection In Sparse Graphs
- Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao, Graphs with 3-Rainbow Index n − 1 and n − 2
- Ingo Schiermeyer, Bounds for the rainbow connection number of graphs
- Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao, Graphs with 4-Rainbow Index 3 and n − 1
- Sandi Klavžar, Gašper Mekiš, On the rainbow connection of Cartesian products and their subgraphs

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.