The complexity of determining the vertex-rainbow index of graphs

DOI10.1142/S1793830915500470zbMath1331.05064OpenAlexW1702314990MaRDI QIDQ2788724

Yongtang Shi, Yaping Mao

Publication date: 22 February 2016

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830915500470

zbMATH Keywords

computational complexityvertex-coloringvertex-rainbow \(S\)-tree\(k\)-vertex rainbow index

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items

Graphs with small total rainbow connection number, A survey on rainbow (vertex-)index of graphs, The vertex-rainbow index of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Rainbow connection in 3-connected graphs
• Further hardness results on the rainbow vertex-connection number of graphs
• On rainbow total-coloring of a graph
• The complexity of determining the rainbow vertex-connection of a graph
• The vertex-rainbow index of a graph
• Note on minimally \(d\)-rainbow connected graphs
• On rainbow connection
• Rainbow connections of graphs: a survey
• Note on the hardness of rainbow connections for planar and line graphs
• Solutions to conjectures on the (k ,ℓ)-rainbow index of complete graphs
• Characterize graphs with rainbow connection number $m-2$ and $m-3$
• Rainbow trees in graphs and generalized connectivity
• Rainbow connection in graphs
• Oriented diameter and rainbow connection number of a graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Hardness and Algorithms for Rainbow Connectivity
• The strong rainbow vertex-connection of graphs