Hardness and Algorithms for Rainbow Connectivity
From MaRDI portal
Publication:5389981
DOI10.4230/LIPIcs.STACS.2009.1811zbMath1236.68080MaRDI 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
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C40: Connectivity
Related Items
Rainbow and strong rainbow connection number for some families of graphs, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, On various (strong) rainbow connection numbers of graphs, Rainbow vertex-connection and graph products, Rainbow connectivity and rainbow index of inhomogeneous random graphs, 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, Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs, On rainbow-\(k\)-connectivity of random graphs, On rainbow total-coloring of a graph, The complexity of determining the rainbow vertex-connection of a graph, Rainbow connection number and radius, Rainbow vertex connection of digraphs, The \(k\)-proper index of graphs, Rainbow connections of graphs: a survey, Multicolorful connectivity of trees, Colorful monochromatic connectivity, Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six, Note on the hardness of rainbow connections for planar and line graphs, Upper bound involving parameter \(\sigma_2\) for the rainbow connection number, The complexity of determining the vertex-rainbow index of graphs, Rainbow connection number and connected dominating sets
