Rainbow and Monochromatic Vertex-connection of Random Graphs.

A vertex-colored path P is rainbow if its internal vertices have distinct colors; whereas P is monochromatic if its internal vertices are colored the same. For a vertex-colored connected graph G, the rainbow vertex-connection number rvc(G) is the minimum number of colors used such that there is a rainbow path joining any two vertices of G; whereas the monochromatic vertex-connection number mvc(G) is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path. These two opposite concepts are the vertex-versions of rainbow connection number rc(G) and monochromatic connection number mc(G) respectively. The study on rc(G) and mc(G) of random graphs drew much attention, and there are few results on the rainbow and monochromatic vertex-connection numbers. In this paper, we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them, respectively. [ABSTRACT FROM AUTHOR]