New Hardness Results in Rainbow Connectivity

DOI10.4230/LIPIcs.FSTTCS.2011.241zbMath1246.68127arXiv1104.2074MaRDI QIDQ2911628

Kanthi K. Sarpatwar, Meghana Nasre, Prabhanjan V. Ananth

Publication date: 31 August 2012

Full work available at URL: https://arxiv.org/abs/1104.2074

zbMATH Keywords

computational complexitygraph theoryrainbow connectivityfixed parameter tractable algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (17)

Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ On the complexity of rainbow coloring problems ⋮ Strong rainbow connection numbers of toroidal meshes ⋮ Rainbow colouring of split graphs ⋮ Rainbow connection number and graph operations ⋮ On the rainbow connectivity of graphs: complexity and FPT algorithms ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Strong rainbow connection in digraphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Generalized rainbow connection of graphs ⋮ Rainbow connections in digraphs ⋮ Generalized rainbow connectivity of graphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Note on the hardness of rainbow connections for planar and line graphs

This page was built for publication: New Hardness Results in Rainbow Connectivity