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

Abstract

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

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.