# Rainbow Vertex-Connection and Forbidden Subgraphs

Wenjing Li; Xueliang Li; Jingshu Zhang

Discussiones Mathematicae Graph Theory (2018)

- Volume: 38, Issue: 1, page 143-154
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.