- Tytuł:
- Vertex rainbow colorings of graphs
- Autorzy:
-
Fujie-Okamoto, Futaba
Kolasinski, Kyle
Lin, Jianwei
Zhang, Ping - Powiązania:
- https://bibliotekanauki.pl/articles/743667.pdf
- Data publikacji:
- 2012
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow path
vertex rainbow coloring
vertex rainbow connection number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2012, 32, 1; 63-80
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł