Displaying similar documents to “On rainbow connection.”

On the Rainbow Vertex-Connection

Xueliang Li, Yongtang Shi (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ...

Rainbow Connection In Sparse Graphs

Arnfried Kemnitz, Jakub Przybyło, Ingo Schiermeyer, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.

Vertex rainbow colorings of graphs

Futaba Fujie-Okamoto, Kyle Kolasinski, Jianwei Lin, Ping Zhang (2012)

Discussiones Mathematicae Graph Theory

Similarity:

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

Fruit salad.

Gyárfás, András (1997)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Rainbow Connection Number of Dense Graphs

Xueliang Li, Mengmeng Liu, Ingo Schiermeyer (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.

Rainbow Vertex-Connection and Forbidden Subgraphs

Wenjing Li, Xueliang Li, Jingshu Zhang (2018)

Discussiones Mathematicae Graph Theory

Similarity:

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