Rainbow Vertex-Connection and Forbidden Subgraphs

Wenjing Li, Xueliang Li, and Jingshu Zhang. "Rainbow Vertex-Connection and Forbidden Subgraphs." Discussiones Mathematicae Graph Theory 38.1 (2018): 143-154. <http://eudml.org/doc/288565>.

@article{WenjingLi2018,
abstract = {A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ \{1, 2\}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.},
author = {Wenjing Li, Xueliang Li, Jingshu Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex-rainbow path; rainbow vertex-connection; forbidden sub-graphs},
language = {eng},
number = {1},
pages = {143-154},
title = {Rainbow Vertex-Connection and Forbidden Subgraphs},
url = {http://eudml.org/doc/288565},
volume = {38},
year = {2018},
}

TY - JOUR
AU - Wenjing Li
AU - Xueliang Li
AU - Jingshu Zhang
TI - Rainbow Vertex-Connection and Forbidden Subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2018
VL - 38
IS - 1
SP - 143
EP - 154
AB - A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
LA - eng
KW - vertex-rainbow path; rainbow vertex-connection; forbidden sub-graphs
UR - http://eudml.org/doc/288565
ER -