Vertex rainbow colorings of graphs

Futaba Fujie-Okamoto; Kyle Kolasinski; Jianwei Lin; Ping Zhang

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 63-80
  • ISSN: 2083-5892

Abstract

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

How to cite

top

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 -

References

top
  1. [1] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  2. [2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81, doi: 10.1002/net.20296. Zbl1205.05124
  3. [3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367. Zbl1205.05085
  4. [4] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, 2009). Zbl1169.05001
  5. [5] M. Krivelevich and R. Yuster,The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191 Zbl1193.05079
  6. [6] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150-168, doi: 10.2307/2371086. Zbl58.0609.01

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.