# Vertex rainbow colorings of graphs

Futaba Fujie-Okamoto; Kyle Kolasinski; Jianwei Lin; Ping Zhang

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 1, page 63-80
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFutaba Fujie-Okamoto, et al. "Vertex rainbow colorings of graphs." Discussiones Mathematicae Graph Theory 32.1 (2012): 63-80. <http://eudml.org/doc/270920>.

@article{FutabaFujie2012,

abstract = {In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number vrc(G) of G. Thus if G is a connected graph of order n ≥ 2, then 2 ≤ vrc(G) ≤ n. We present characterizations of all connected graphs G of order n for which vrc(G) ∈ \{2,n-1,n\} and study the relationship between vrc(G) and the chromatic number χ(G) of G. For a connected graph G of order n and size m, the number m-n+1 is the cycle rank of G. Vertex rainbow connection numbers are determined for all connected graphs of cycle rank 0 or 1 and these numbers are investigated for connected graphs of cycle rank 2.},

author = {Futaba Fujie-Okamoto, Kyle Kolasinski, Jianwei Lin, Ping Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {rainbow path; vertex rainbow coloring; vertex rainbow connection number},

language = {eng},

number = {1},

pages = {63-80},

title = {Vertex rainbow colorings of graphs},

url = {http://eudml.org/doc/270920},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Futaba Fujie-Okamoto

AU - Kyle Kolasinski

AU - Jianwei Lin

AU - Ping Zhang

TI - Vertex rainbow colorings of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 1

SP - 63

EP - 80

AB - In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number vrc(G) of G. Thus if G is a connected graph of order n ≥ 2, then 2 ≤ vrc(G) ≤ n. We present characterizations of all connected graphs G of order n for which vrc(G) ∈ {2,n-1,n} and study the relationship between vrc(G) and the chromatic number χ(G) of G. For a connected graph G of order n and size m, the number m-n+1 is the cycle rank of G. Vertex rainbow connection numbers are determined for all connected graphs of cycle rank 0 or 1 and these numbers are investigated for connected graphs of cycle rank 2.

LA - eng

KW - rainbow path; vertex rainbow coloring; vertex rainbow connection number

UR - http://eudml.org/doc/270920

ER -

## References

top- [1] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
- [2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81, doi: 10.1002/net.20296. Zbl1205.05124
- [3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367. Zbl1205.05085
- [4] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, 2009). Zbl1169.05001
- [5] M. Krivelevich and R. Yuster,The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191 Zbl1193.05079
- [6] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168, doi: 10.2307/2371086. Zbl58.0609.01

## NotesEmbed ?

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