Note on the vertex-rainbow index of a graph
type: Item
instance of: scholarly article
title: Note on the vertex-rainbow index of a graph
zbMATH Open document ID: 1473.05099
author: Yan Zhao
author: Fengwei Li
author: Xiaoyan Zhang
published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series
publication date: 2021-08-24T00:00:00Z
review text: Let \(G\) be a graph and let \(S\) be arbitrary \(k\)-subset of \(V(G)\) for some \(k\in\{2,3,\dots,|V(G)|\}\). An \(S\)-tree is any subtree of \(G\) that contains all vertices from \(S\). A vertex coloring, that is not necessarily a proper coloring, is called a \(k\)-vertex-rainbow coloring if there exists an \(S\)-tree such that all the vertices of \(V(T)-S\) have different coloring for any \(k\)-subset \(S\) of \(V(G)\). The minimum number of colors in such a coloring is then called \(k\)-vertex rainbow index and is denoted by \(rvx_k(G)\). The main result of this note is that \(rvx_3(G)>\frac{3|V(G)|}{\delta}+16\) holds for a connected graph \(G\) with minimum degree \(\delta\). On the case of cycles, the authors also show that the \(k\)-vertex rainbow index is not hereditary with respect to \(k\).
reviewed by: Iztok Peterin
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 7384658
zbMATH Keywords: vertex-rainbow coloring
zbMATH Keywords: vertex-rainbow index
MaRDI profile type: Publication
full work available at URL: s40840-021-01092-0
OpenAlex ID: W3135786273
cites work: Q5422499
cites work: Rainbow connection in graphs
cites work: The vertex-rainbow index of a graph
cites work: On rainbow connection
cites work: Rainbow trees in graphs and generalized connectivity
cites work: The rainbow connectivity of a graph
cites work: The rainbow connection of a graph is (at most) reciprocal to its minimum degree
cites work: Rainbow connection number and graph operations
cites work: Rainbow connection numbers of middle and total graphs
cites work: Tight upper bound of the rainbow vertex-connection number for 2-connected graphs
cites work: Rainbow connections of graphs: a survey
cites work: On total rainbow \(k\)-connected graphs
cites work: Spanning Trees with Many Leaves
cites work: Spanning trees in graphs of minimum degree 4 or 5
DOI: 10.1007/S40840-021-01092-0
description: scientific article; zbMATH DE number 7384658