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.05143OpenAlexW2551296270MaRDI 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
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items
Hardness results for total rainbow connection of graphs, Graphs with small total rainbow connection number, The strong 3-rainbow index of some certain graphs and its amalgamation, The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles, On the complexity of \(k\)-rainbow cycle colouring problems, Rainbow vertex-connection and forbidden subgraphs, A survey on rainbow (vertex-)index of graphs, Further hardness results on rainbow and strong rainbow connectivity, 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, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, On total rainbow \(k\)-connected graphs, Coupon coloring of some special graphs, The complexity of determining the vertex-rainbow index of graphs, On various (strong) rainbow connection numbers of graphs, A characterisation on arc-transitive graphs of prime valency, Rainbow connectivity and rainbow criticality on graph classes
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