# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## 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.