Further hardness results on the rainbow vertex-connection number of graphs

DOI10.1016/J.TCS.2013.02.012zbMath1291.68174arXiv1110.1915OpenAlexW2962805443MaRDI QIDQ385046

Lily Chen, Hui-shu Lian, Xue Liang Li

Publication date: 29 November 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.1915

zbMATH Keywords

NP-hardNP-completerainbow vertex-connection numbervertex-colored graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (12)

Algorithms for the rainbow vertex coloring problem on graph classes ⋮ Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs ⋮ Upper bounds for the total rainbow connection of graphs ⋮ On the complexity of rainbow coloring problems ⋮ Tight upper bound of the rainbow vertex-connection number for 2-connected graphs ⋮ A survey on rainbow (vertex-)index of graphs ⋮ The vertex-rainbow connection number of some graph operations ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ The complexity of determining the vertex-rainbow index of graphs ⋮ On various (strong) rainbow connection numbers of graphs ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

Cites Work

• Unnamed Item
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

This page was built for publication: Further hardness results on the rainbow vertex-connection number of graphs