Note on the vertex-rainbow index of a graph (Q2048994): Difference between revisions
From MaRDI portal
Latest revision as of 11:52, 26 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Note on the vertex-rainbow index of a graph |
scientific article |
Statements
Note on the vertex-rainbow index of a graph (English)
0 references
24 August 2021
0 references
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\).
0 references
vertex-rainbow coloring
0 references
vertex-rainbow index
0 references