Further hardness results on rainbow and strong rainbow connectivity
From MaRDI portal
Publication:908308
DOI10.1016/j.dam.2015.07.041zbMath1329.05171arXiv1404.3082OpenAlexW1920882336MaRDI QIDQ908308
Publication date: 4 February 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.3082
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (8)
On finding rainbow and colorful paths ⋮ On the complexity of rainbow coloring problems ⋮ On the complexity of \(k\)-rainbow cycle colouring problems ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Algorithm on rainbow connection for maximal outerplanar graphs ⋮ Rainbow connectivity of Moore cages of girth 6
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Hardness and algorithms for rainbow connection
- The complexity of determining the rainbow vertex-connection of a graph
- A simplified NP-complete satisfiability problem
- Rainbow connections of graphs: a survey
- Grad and classes with bounded expansion. I: Decompositions
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- New Hardness Results in Rainbow Connectivity
- New Races in Parameterized Algorithmics
- Inapproximability of Rainbow Colouring
- Rainbow connection in graphs
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- The rainbow connection of a graph is (at most) reciprocal to its minimum degree
- The strong rainbow vertex-connection of graphs
- On planar geodetic graphs
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: Further hardness results on rainbow and strong rainbow connectivity