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
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
