Discussiones Mathematicae Graph Theory 32(2) (2012) 63-80
doi: 10.7151/dmgt.1586

[BIBTex] [PDF] [PS]

Vertex Rainbow Colorings of Graphs

Futaba Fujie-Okamoto

Mathematics Department
University of Wisconsin La Crosse
La Crosse, WI 54601, USA

Kyle Kolasinski, Jianwei Lin, Ping Zhang

Department of Mathematics
Western Michigan University
Kalamazoo, MI 49008, USA

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.

Keywords: rainbow path, vertex rainbow coloring, vertex rainbow connection number

2010 Mathematics Subject Classification: 05C15, 05C40.

References

[1]G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85--98.
[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.
[3]G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360--367.
[4]G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, 2009).
[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
[6]H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150--168, doi: 10.2307/2371086.

Received 15 June 2010
Revised 20 January 2011
Accepted 24 January 2011