Complexity of rainbow vertex connectivity problems for restricted graph classes
From MaRDI portal
Publication:505435
DOI10.1016/j.dam.2016.11.023zbMath1354.05049arXiv1612.07768MaRDI QIDQ505435
Publication date: 23 January 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1612.07768
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C40: Connectivity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Fundamentals of parameterized complexity
- Further hardness results on the rainbow vertex-connection number of graphs
- Rainbow connection in oriented graphs
- Hardness and algorithms for rainbow connection
- The complexity of determining the rainbow vertex-connection of a graph
- A simplified NP-complete satisfiability problem
- Further hardness results on rainbow and strong rainbow connectivity
- Bigeodetic graphs
- A partial k-arboretum of graphs with bounded treewidth
- On the complexity of rainbow coloring problems
- Rainbow connections of graphs: a survey
- Topology of series-parallel networks
- Grad and classes with bounded expansion. I: Decompositions
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- New Races in Parameterized Algorithmics
- Rainbow connection in graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- 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
- Parameterized Algorithms
- On planar geodetic graphs
- A Characterization of Comparability Graphs and of Interval Graphs
