Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs

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

zbMATH Keywords

bipartite graphNP-completenesspolynomial timerainbow vertex-connectionstrong rainbow connection

Mathematics Subject Classification ID

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