Hardness and Algorithms for Rainbow Connectivity
From MaRDI portal
Publication:5389981
DOI10.4230/LIPICS.STACS.2009.1811zbMath1236.68080OpenAlexW2282096084MaRDI QIDQ5389981
Raphael Yuster, Arie Matsliah, Sourav Chakraborty, Eldar Fischer
Publication date: 24 April 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_8b44.html
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (23)
Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ Sufficient conditions for 2-rainbow connected graphs ⋮ Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs ⋮ Rainbow connection number and connected dominating sets ⋮ Rainbow connectivity and rainbow index of inhomogeneous random graphs ⋮ Rainbow connections of graphs: a survey ⋮ Rainbow vertex connection of digraphs ⋮ Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs ⋮ On rainbow-\(k\)-connectivity of random graphs ⋮ The complexity of determining the rainbow vertex-connection of a graph ⋮ Upper bound involving parameter \(\sigma_2\) for the rainbow connection number ⋮ The \(k\)-proper index of graphs ⋮ Rainbow and strong rainbow connection number for some families of graphs ⋮ On rainbow total-coloring of a graph ⋮ Multicolorful connectivity of trees ⋮ Rainbow vertex-connection and graph products ⋮ The rainbow connection of a graph is (at most) reciprocal to its minimum degree ⋮ Colorful monochromatic connectivity ⋮ The complexity of determining the vertex-rainbow index of graphs ⋮ On various (strong) rainbow connection numbers of graphs ⋮ Rainbow connection number and radius ⋮ Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six ⋮ Note on the hardness of rainbow connections for planar and line graphs
This page was built for publication: Hardness and Algorithms for Rainbow Connectivity
