Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
From MaRDI portal
Publication:300179
DOI10.1016/j.amc.2015.02.015zbMath1338.05143MaRDI QIDQ300179
Shasha Li, Yongtang Shi, Xue Liang Li
Publication date: 23 June 2016
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.amc.2015.02.015
bipartite graph; NP-completeness; polynomial time; rainbow vertex-connection; strong rainbow connection
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
The strong 3-rainbow index of some certain graphs and its amalgamation, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, On various (strong) rainbow connection numbers of graphs, A survey on rainbow (vertex-)index of graphs, Hardness results for total rainbow connection of graphs, Coupon coloring of some special graphs, Further hardness results on rainbow and strong rainbow connectivity, The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles, Rainbow vertex-connection and forbidden subgraphs, A result on the 3-generalized connectivity of a graph and its line graph, Note on the perfect EIC-graphs, The \(k\)-proper index of graphs, On tetravalent symmetric dihedrants, On total rainbow \(k\)-connected graphs, Rainbow connectivity and rainbow criticality on graph classes, A characterisation on arc-transitive graphs of prime valency, Graphs with small total rainbow connection number, On the complexity of \(k\)-rainbow cycle colouring problems, The complexity of determining the vertex-rainbow index of graphs
Cites Work
- Unnamed Item
- Further hardness results on the rainbow vertex-connection number of graphs
- The complexity of determining the rainbow vertex-connection of a graph
- On rainbow connection
- Rainbow connections of graphs: a survey
- New Hardness Results in Rainbow Connectivity
- Rainbow connection in graphs
- The rainbow connection of a graph is (at most) reciprocal to its minimum degree
- Hardness and Algorithms for Rainbow Connectivity
