Vertex rainbow colorings of graphs

Futaba 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 -